var
a:array [1..60,1..60,1..2] of longint;
f:array [0..32000] of longint;
b:array [1..60] of longint;
i,j,m,n,k,s,w,v,q:longint;
begin
read(n,m);
for i:=1 to m do
b[i]:=1;
for i:=1 to m do
begin
read(w,v,q);
if q=0 then
begin
inc(s);
a[s,1,1]:=w;
a[s,1,2]:=w*v
end
else
begin
inc(b[q]);
a[q,b[q],1]:=w;
a[q,b[q],2]:=w*v;
inc(b[q])
end
end;
for i:=1 to s do
for j:=n downto 0 do
begin
if (j>a[i,1,1]) and (f[j]<f[j-a[i,1,1]]+a[i,1,2]) then
f[j]:=f[j-a[i,1,1]]+a[i,1,2];
if (j>a[i,1,1]+a[i,2,1]) and (f[j]<f[j-a[i,1,1]-a[i,2,1]]+a[i,1,2]+a[i,2,2]) then
f[j]:=f[j-a[i,1,1]-a[i,2,1]]+a[i,1,2]+a[i,2,2];
if (j>a[i,1,1]+a[i,3,1]) and (f[j]<f[j-a[i,1,1]-a[i,3,1]]+a[i,1,2]+a[i,3,2]) then
f[j]:=f[j-a[i,1,1]-a[i,3,1]]+a[i,1,2]+a[i,3,2];
if (j>a[i,1,1]+a[i,2,1]+a[i,3,1]) and (f[j]<f[j-a[i,1,1]-a[i,2,1]-a[i,3,1]]+a[i,1,2]+a[i,2,2]+a[i,3,2]) then
f[j]:=f[j-a[i,1,1]-a[i,2,1]-a[i,3,1]]+a[i,1,2]+a[i,2,2]+a[i,3,2]
end;
writeln(f[n])
end.
数组a表示第i个物品的第k个附件的费用和价值
比如a[1,1,2]表示第1个物品主件的价值
a[1,1,1] 表示第1个物品主件的费用
a[2,2,1]就表示第2个物品的第1个附件的费用
s就是一共多少个主件(我把附件全套在主件后头了- -)
然后就是DP枚举4种决策。。。
结果总是wa
求大神看看哪错了???
把(j>a[i,1,1])改成(j>=a[i,1,1])也AC不了,才60分。。。