/ Vijos / 题库 / GF /

题解

50 条题解

  • 0
    @ 2009-08-22 16:20:55

    我第 250 个通过。。。

  • 0
    @ 2009-08-09 11:41:15

    如对本题有疑问可以参看我的题解:http://xujieqi.blog.hexun.com/35722312_d.html

  • 0
    @ 2009-08-08 11:43:57

    很爽的菜题,适合我这种小菜了,,,,

    这家伙够狠,把MM套进背包里。。。。。。。。。。。

  • 0
    @ 2009-08-01 14:09:15

    题目虽然比较基础,但是做起来还是蛮有心得的

    温故而知新

  • 0
    @ 2009-07-25 15:54:52

    f[j,k]=f[j-w[i],k-r[i]]+1写成了f[j,k]=f[j-w[i],k-r[i]+1]居然也有70分,数据弱的让我无语了.

  • 0
    @ 2009-07-19 15:04:41

    二维背包

    编译通过...

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

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

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

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

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

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

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

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

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

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

    var n,m,r,i,j,k:longint;

    rm,rp:array[0..101] of longint;

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

    f,t:array[0..101,0..101] of longint;

    function min(a,b:longint):longint;

    begin

    if a>b then min:=a

    else min:=b;

    end;

    begin

    readln(n);

    for i:=1 to n do

    begin

    read(rm[i],rp[i],ti[i]);

    readln;

    end;

    read(m,r);

    for i:=1 to n do

    for j:=m downto rm[i] do

    for k:=r downto rp[i] do

    if (f[j,k]t[j-rm[i],k-rp[i]]+ti[i])) then

    begin

    f[j,k]:=f[j-rm[i],k-rp[i]]+1;

    t[j,k]:=t[j-rm[i],k-rp[i]]+ti[i];

    end;

    writeln(t[m,r]);

    end.

  • 0
    @ 2009-07-14 08:24:25

    背包

  • 0
    @ 2009-07-11 20:09:52

    楼下的,语言不通啊 看不懂 倒是楼下的楼下很强

    1个小时AC 我最终还是成功的搞混了f中i,j的含义,并成功的把num和f搞混,调了我20+min...

    这道题还是很经典的,对我这种菜很值得一做。再做DP一定要注意各个变量的含义,还有细致,小错误过了样例,结果A了两个点。自己编数据还有有必要的。

    注意:就算num不更新,f也有可能更新 else if (max=num) and (min>f) then min:=f;

  • 0
    @ 2009-07-03 23:47:31

    题解:

  • 0
    @ 2009-07-03 18:45:35

    AC 标程 仅供参考。

    谢谢。

    朽木可雕,大牛可教。

    超越梦想,不是梦想,相信自己的力量!!!

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    program P1544;

    var

    n,m,i,j,k,r :longint;

    ans1,t,l,ans2 :longint;

    a :array[1..100,1..3]of longint;

    f1,f2 :array[0..100,0..100]of longint;

    begin

    readln(n);

    for i:=1 to n do readln(a,a,a);

    readln(m,r);

    fillchar(f1,sizeof(f1),0);

    fillchar(f2,sizeof(f2),127);

    ans1:=0; ans2:=maxlongint; f2[0,0]:=0;

    for i:=1 to n do

    for j:=m downto a do

    for k:=r downto a do

    if (f1[j,k]f2[j-a,k-a]+a)) then

    begin

    f1[j,k]:=f1[j-a,k-a]+1;

    f2[j,k]:=f2[j-a,k-a]+a;

    if ans1f2[j,k]) then begin ans2:=f2[j,k]; continue; end;

    end;

    writeln(ans2);

    end.

  • 0
    @ 2009-06-20 18:28:15

    给个代码,大家有兴趣的可以参考一下,不过不是很好啊!

    大牛们别怪我!

    var rmb,rp:array[1..100] of longint;

    time:array[1..1000] of longint;

    f,a:array[0..100,0..100] of longint;

    n,m,r:longint;

    i,j,k:longint;

    min,max:longint;

    begin

    readln(n);

    for i:=1 to n do

    begin

    readln(rmb[i],rp[i],time[i]);

    end;

    readln(m,r);

    for i:=0 to m do

    for j:=0 to r do

    begin

    f:=maxint;

    f[0,0]:=0;

    end;

    for i:=1 to n do

    for j:=m downto rmb[i] do

    for k:=r downto rp[i] do

    if (a[j,k]f[j-rmb[i],k-rp[i]]+time[i])

    and (a[j,k]=a[j-rmb[i],k-rp[i]]+1)) then

    begin

    f[j,k]:=f[j-rmb[i],k-rp[i]]+time[i];

    a[j,k]:=a[j-rmb[i],k-rp[i]]+1;

    end;

    min:=maxint; max:=0;

    for i:=1 to m do

    for j:=1 to r do

    if (max

  • 0
    @ 2009-06-18 13:39:07

    AC!!!

    a[j,k]:=a[j-rmb[i],k-rp[i]]+1;

    f[j,k]:=f[j-rmb[i],k-rp[i]]+time[i];

    要注意 时间1>时间2 AND 数量1=数量2 THEN 时间1=时间2

  • 0
    @ 2009-06-12 16:59:38

    一般来说这种水题用来了练习C++语法。。。

  • 0
    @ 2009-06-08 21:45:50

    是“NASA的食物计划”的加强版,不过还是水题^-^

  • 0
    @ 2009-06-06 23:15:49

    最多MM的最少时间?这句话让我很迷茫

  • 0
    @ 2009-06-06 07:50:46

    很好很水很有趣

    话说以前在RQ上面做过

  • 0
    @ 2009-07-04 21:08:44

    第60个ac

    一次ac,这种水题放在Vijos上也好,可以锻炼初学者的DP能力。

    关键代码:

    for (k=1;k=rmb[k];i--)

    for (j=r;j>=rp[k];j--)

    if(t[i-rmb[k]][j-rp[k]]+1>t[i][j])

    {t[i][j]=t[i-rmb[k]][j-rp[k]]+1;

    f[i][j]=f[i-rmb[k]][j-rp[k]]+time[k];

    }

    else if(t[i-rmb[k]][j-rp[k]]+1==t[i][j]) f[i][j]=min1(f[i][j],f[i-rmb[k]][j-rp[k]]+time[k]);

    具体关于二维背包的问题,请参阅“背包问题九讲”的相关内容。

    点击这里看解题报告

  • 0
    @ 2009-06-05 17:19:51

    注意要特判下f=f+1的情况下time的取值

    取最小的time)

    很关键的地方。

  • 0
    @ 2009-06-05 16:36:34

    简单双重背包 一次AC

    枚举rmb和rp求解即可

  • 0
    @ 2009-06-05 16:25:54

    一个背包题目,交第一遍时没考虑f=f+1的情况,哎!

信息

ID
1544
难度
4
分类
动态规划 点击显示
标签
(无)
递交数
1427
已通过
592
通过率
41%
被复制
3
上传者