var f1:array[0..100,0..100,0..100] of integer;
f2:array[0..100,0..100,0..100] of longint;
time,rmb,rp:array[1..100] of integer;
n,m,r1,i,j,k:integer;
min:longint;
begin
readln(n);
for i:=1 to n do
readln(rmb[i],rp[i],time[i]);
readln(m,r1);
for i:=1 to n do
for j:=rmb[i] to m do
for k:=rp[i] to r1 do
begin
f1[i,j,k]:=f1[i-1,j,k];
f2[i,j,k]:=f2[i-1,j,k];
if (f1[i-1,j-rmb[i],k-rp[i]] + 1 > f1[i,j,k])
or (f1[i-1,j-rmb[i],k-rp[i]] + 1 = f1[i,j,k])
and (f2[i-1,j-rmb[i],k-rp[i]] + time[i] < f2[i,j,k]) then
begin
f1[i,j,k]:=f1[i-1,j-rmb[i],k-rp[i]] + 1;
f2[i,j,k]:=f2[i-1,j-rmb[i],k-rp[i]] + time[i];
end;
end;
writeln(f2[n,m,r1]);
//writeln(f1[n,m,r1]);
//readln
end.
其中f1记录最多MM数,f2记录最少TIME。
if (f1[i-1,j-rmb[i],k-rp[i]] + 1 > f1[i,j,k])
or (f1[i-1,j-rmb[i],k-rp[i]] + 1 = f1[i,j,k])
and (f2[i-1,j-rmb[i],k-rp[i]] + time[i] < f2[i,j,k])
这句的含义是如果可以得到更多MM 或 得到MM数相同但是消耗时间更少时,进行更新
program rq57;
var f1:array[0..100,0..100] of integer;
f2:array[0..100,0..100] of longint;
time,rmb,rp:array[1..100] of integer;
n,m,r1,i,j,k:integer;
begin
readln(n);
for i:=1 to n do
readln(rmb[i],rp[i],time[i]);
readln(m,r1);
f1[0,0]:=0;
for i:=1 to n do
for j:=m downto rmb[i] do
for k:=r1 downto rp[i] do
begin
if (f1[j-rmb[i],k-rp[i]] + 1 > f1[j,k])
or (f1[j-rmb[i],k-rp[i]] + 1 = f1[j,k])
and (f2[j-rmb[i],k-rp[i]] + time[i] < f2[j,k]) then
begin
f1[j,k]:=f1[j-rmb[i],k-rp[i]] + 1;
f2[j,k]:=f2[j-rmb[i],k-rp[i]] + time[i];
end;
end;
writeln(f2[m,r1]);
//writeln(f1[n,m,r1]);
//readln
end.
依旧不理解,望牛人解疑!
因为循环的范围 [m,rmb[i]]和[r,rp[i]]所以一部分数据没办法传到下一阶段。
也就是下面这两句没有起到应有的作用。
f1[i,j,k]:=f1[i-1,j,k];
f2[i,j,k]:=f2[i-1,j,k];
例如下面的测试数据:
6
1 2 5
2 1 6
10 10 10
10 10 10
2 2 2
2 2 3
5 5
正确答案应该是 13 错误答案可能是5
所以,循环要改成
for j:=0 to m do
for k:=0 to r do
然后多一个 判断 看是否大于ram[i],rp[i] 来决定是否比较。
上一阶段的还是要传给下一阶段,只不过那两句要放在判断前...
即:
for ..............
for ................
f1[x,x,x]:=f1[x-1,x,x]
f2[.......]:=f2[...........]
if (j>=...)and( k>=....) then
if( ............>.........+... )or(.....)and(...)then
begin
................
end;