题解

64 条题解

  • 4
    @ 2016-11-07 19:14:08

    这是第一个c++题解吗。。。

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    using namespace std ;
    const int maxn = 6001,inf = 0x7f7f7f7f;
    int f[maxn],a[1010],b[1010];
    int main () {
        int  k,m = 0,n,sum = 0;
        scanf ("%d",&n); 
        for (int i=1;i<=n;i++) {
            scanf ("%d%d",a+i,b+i);
            m += max(a[i],b[i]); 
            sum += a[i] + b[i]; 
        }
        memset (f,inf,sizeof f); 
        f[0] = 0; 
        for (int i=1;i<=n;i++) 
            for (int j=m;j>=0;j--) {
                int ans = inf; 
                if ( j >= a[i] )
                    ans = f[j-a[i]];
                if ( j >= b[i] )
                    ans = min(ans,f[j-b[i]]+1);
                f[j] = ans;
            }
        for (int i=sum>>1;i;i--) {
            k = min(f[i],f[sum-i]);
            if ( k < inf ) {
                printf("%d\n",k) ;
                return 0 ;
            }
        }
        return 0 ;
    }
    
  • 1
    @ 2019-03-26 20:09:25

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    using namespace std ;
    const int maxn = 6001,inf = 0x7f7f7f7f;
    int f[maxn],a[1010],b[1010];
    int main () {
    int k,m = 0,n,sum = 0;
    scanf ("%d",&n);
    for (int i=1;i<=n;i++) {
    scanf ("%d%d",a+i,b+i);
    m += max(a[i],b[i]);
    sum += a[i] + b[i];
    }
    memset (f,inf,sizeof f);
    f[0] = 0;
    for (int i=1;i<=n;i++)
    for (int j=m;j>=0;j--) {
    int ans = inf;
    if ( j >= a[i] )
    ans = f[j-a[i]];
    if ( j >= b[i] )
    ans = min(ans,f[j-b[i]]+1);
    f[j] = ans;
    }
    for (int i=sum>>1;i;i--) {
    k = min(f[i],f[sum-i]);
    if ( k < inf ) {
    printf("%d\n",k) ;
    return 0 ;
    }
    }
    return 0 ;
    }

  • 1
    @ 2016-05-19 16:59:12
  • 1
    @ 2006-09-12 20:05:31

    法一:

    本问题可归约为经典的背包问题。

    假设一碗拉面的重量差的绝对值是s,那么它实际可以取到的重量差就是-s或s。我们不妨对取值进行一下平移,让每碗拉面可以取到的点数差为0和2s。这样,拉面的“取正值还是负值”就转化为背包的“取与不取”了。

    那么,我们求解的目标会怎样变化呢?本来,我们的目标是让取值的总和为0。现在,我们对每碗拉面的取值作了平移,平移的距离为s。那么,最后的取值总和就应该是∑s,即所有拉面的平移距离之和。

    方法二:

    我们用数组a[ i]表示第i碗拉面的上下重量之差,用F表示用前i 碗拉面上下差值为j时所要的最少操作次数,那么有

    f:=min(f[i-1,j-a[ i]],f[i-1,j+a[ i]]+1);

    最后的答案为f[n,k],其中k是最接近0的可能得到的数值。

    考虑到空间问题,数组可以采用滚动数组实现

  • 0
    @ 2016-02-26 19:57:12

    f[i][j]表示前i个数,换j次的绝对值最小时对应的值,过了8个点
    f[i][j]表示前i个数,得到差为j时的最小换的次数,ac
    求教原因。。。

  • 0
    @ 2013-10-30 15:47:17

    const t=2500;
    var
    f,ff:array[-t..t] of boolean;
    s,ss:array[-t..t] of longint;
    n,i,x,y,l:longint;
    function min(a,b:longint):longint;
    begin
    if a<b then exit(a);
    exit(b);
    end;
    function ok(k:longint):boolean;
    begin
    if (k>=-2500) and (k<=2500) then exit(true);
    exit(false);
    end;
    begin
    readln(n);
    fillchar(f,sizeof(f),false);
    fillchar(s,sizeof(s),\(7f);
    readln(x,y);
    f[x-y]:=true;s[x-y]:=0;
    f[y-x]:=true;s[y-x]:=1;
    for l:=2 to n do
    begin
    readln(x,y);
    fillchar(ff,sizeof(ff),false);
    fillchar(ss,sizeof(ss),\)7f);
    for i:=-t to t do
    if f[i] then
    begin
    if ok(i+x-y) then
    begin
    ff[i+x-y]:=true;
    if ss[i+x-y]>s[i] then ss[i+x-y]:=s[i];

    end;
    if ok(i-x+y) then
    begin
    ff[i-x+y]:=true;
    if ss[i-x+y]>s[i]+1 then ss[i-x+y]:=s[i]+1;
    end;
    end;
    f:=ff;
    s:=ss;
    end;
    for i:=0 to t do
    begin
    if f[i] and f[-i] then
    begin
    writeln(min(s[i],s[-i]));
    halt;
    end;
    if f[i] then
    begin
    writeln(s[i]);
    halt;
    end;
    if f[-i] then
    begin
    writeln(s[-i]);
    halt;
    end;
    end;
    end.
    其实也可以只开s数组,我为了方便。
    第一遍交的时候,我搞错了一个地方:
    我没有用滚动数组,直接在f和s上递推,只对了两个点。
    但其实,第三个是不能从第一个直接转移,必须经过第二个可能的两种变换得到。
    秒过。

  • 0
    @ 2010-04-16 09:30:20

    asdf

  • 0
    @ 2009-11-09 21:33:32

    滚动数组 + 遍读入遍处理 就可以秒杀了~

    题解

    http://hi.baidu.com/%C4%BE%D7%D3%C8%D5%D4%C8/blog/item/349e693cdfe4710abaa167f9.html

  • 0
    @ 2009-11-08 09:52:54

    事实证明:

    开两个数组f1,f2:array[-2600..2600]就好!

    因为下一个的状态 只由上一个推来,所以用两个数组滚动就行。

    因为1

  • 0
    @ 2009-11-04 16:27:04

    f表示前i碗,上部比下部重j的最小操作数。

    f=min{f,f+1}

    边读变做,a和b均为当前读入的值。使用滚动数组能有效降低空间复杂度, 不用也能过。

    初始化:fillchar(f,sizeof(f),$7f div 10);f[0,0]=0;

    总耗时(6K):130ms

  • 0
    @ 2009-11-04 11:56:02

    糟糕,赋初值出问题...

    将搜索范围限定在-5*i..5*i很有效!

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 72ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 56ms

    ├ 测试数据 09:答案正确... 40ms

    ├ 测试数据 10:答案正确... 72ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:240ms

  • 0
    @ 2009-10-27 10:45:38

    我们学校为了“方便学生”在吃饭的时候封校!这就是差距啊!

  • 0
    @ 2009-10-21 19:04:22

    program p1222;

    var f:array[0..1000,-5000..5000] of longint;

    a:array[0..1000] of longint;

    i,j,k,l,m,n,o,p,q,min:longint;

    function max(x,y:longint):longint;

    begin if x

  • 0
    @ 2009-10-21 17:56:08

    10分钟、、、没秒杀、我是沙茶、、、

  • 0
    @ 2009-10-17 20:59:53

    折寿

  • 0
    @ 2009-10-17 18:04:25

    背包今天穿上了拉面的马甲

  • 0
    @ 2009-10-02 17:08:23

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案错误... ├ 标准行输出 352

     ├ 错误行输出 543

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分:90 有效耗时:0ms

    怎么回事???????????????????????????

  • 0
    @ 2009-09-24 13:01:26

    背包+滚动数组就可以秒杀了

  • 0
    @ 2009-09-19 23:38:41

    装箱。。。

    用了传说中的“不复制滚动数组” 0.0|||

    纯粹的滚动式装箱。。。

  • 0
    @ 2009-09-19 12:43:10

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    小菜小菜,一次Ac!

    用户信息 User Info

    超子

    ---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|--

    Level Member

    提交 200次

    通过 66题

    通过率 33%

    program v1222;

    var a:array[0..1001] of shortint;

    f:array[0..1001,-6000..6000] of dword;

    i,j,k,n,x,y,w:longint;

    function min(p,q:longint):longint;

    begin

    if p

信息

ID
1222
难度
5
分类
动态规划 点击显示
标签
(无)
递交数
1315
已通过
419
通过率
32%
被复制
2
上传者