我第 250 个通过。。。

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

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

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

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

温故而知新

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

二维背包

编译通过...

├ 测试数据 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.

背包

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

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

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

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

题解：

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.

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

大牛们别怪我！

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

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

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

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

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

很好很水很有趣

话说以前在RQ上面做过

第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]);

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

点击这里看解题报告

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

取最小的time）

很关键的地方。

简单双重背包 一次AC

枚举rmb和rp求解即可

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