var m,n,i,j,x1,x2,x3,p:longint;
v,q:array[0..60,0..2]of longint;
f:array[0..32000]of longint;
begin
readln(n,m);
fillchar(v,sizeof(v),0);
fillchar(q,sizeof(q),0);
fillchar(f,sizeof(f),0);
n:=n div 10;
for i:=1 to m do
begin
readln(x1,x2,x3);
x1:=x1 div 10;
if x3=0 then begin inc(p);v[p,0]:=x1;q[p,0]:=x2;end
else if v[x3,1]=0 then begin v[x3,1]:=x1;q[x3,1]:=x2;end
else begin v[x3,2]:=x1;q[x3,2]:=x2;end;
end;
for i:=1 to p do
for j:=n downto 0 do
begin
if (j-v[i,0]>0)and(f[j]<f[j-v[i,0]]+v[i,0]*q[i,0])then f[j]:=f[j-v[i,0]]+v[i,0]*q[i,0];
if v[i,1]<>0then if(j-v[i,0]-v[i,1]>0)and(f[j]<f[j-v[i,0]-v[i,1]]+v[i,0]*q[i,0]+v[i,1]*q[i,1])
then f[j]:=f[j-v[i,0]-v[i,1]]+v[i,0]*q[i,0]+v[i,1]*q[i,1]else continue;
if v[i,2]<>0then if(j-v[i,0]-v[i,2]>0)and(f[j]<f[j-v[i,0]-v[i,2]]+v[i,0]*q[i,0]+v[i,2]*q[i,2])
then f[j]:=f[j-v[i,0]-v[i,2]]+v[i,0]*q[i,0]+v[i,2]*q[i,2]else continue;
if v[i,2]<>0then if(j-v[i,0]-v[i,1]-v[i,2]>0)and(f[j]<f[j-v[i,0]-v[i,1]-v[i,2]]+v[i,0]*q[i,0]+v[i,1]*q[i,1]+v[i,2]*q[i,2])
then f[j]:=f[j-v[i,0]-v[i,1]-v[i,2]]+v[i,0]*q[i,0]+v[i,1]*q[i,1]+v[i,2]*q[i,2]else continue;
end;
writeln(f[n]*10);
end.
帮帮忙吧!
状态: Unaccepted
测评机: Xeost[5]
得分: 70分
提交日期: 2010-9-19 23:35:00
有效耗时: 453毫秒
测试结果1: 通过本测试点|有效耗时172ms
测试结果2: 测试结果错误.错误结果为:5200
正确结果应为:6200
测试结果3: 通过本测试点|有效耗时47ms
测试结果4: 通过本测试点|有效耗时47ms
测试结果5: 通过本测试点|有效耗时47ms
测试结果6: 通过本测试点|有效耗时47ms
测试结果7: 通过本测试点|有效耗时47ms
测试结果8: 通过本测试点|有效耗时46ms
测试结果9: 测试结果错误.错误结果为:95400
正确结果应为:96000
测试结果10: 测试结果错误.错误结果为:120200
正确结果应为:120800
program jinming;
var m,n,i,j,x1,x2,x3,p:longint;
v,q:array[0..60,0..2]of longint;
f:array[0..32000]of longint;
g:array[1..60]of longint;
begin
readln(n,m);
fillchar(v,sizeof(v),0);
fillchar(q,sizeof(q),0);
fillchar(f,sizeof(f),0);
n:=n div 10;
for i:=1 to m do
begin
readln(x1,x2,x3);
x1:=x1 div 10;
if x3=0 then begin inc(p);v[p,0]:=x1;q[p,0]:=x2*x1;g[i]:=p;end
else if v[g[x3],1]=0 then begin v[g[x3],1]:=x1;q[g[x3],1]:=x2*x1;end
else begin v[g[x3],2]:=x1;q[g[x3],2]:=x2*x1;end;
end;
for i:=1 to p do
for j:=n downto 0 do
begin
if (j-v[i,0]>0)and(f[j]<f[j-v[i,0]]+q[i,0])then f[j]:=f[j-v[i,0]]+q[i,0];
if v[i,1]>0then if(j-v[i,0]-v[i,1]>0)and(f[j]<f[j-v[i,0]-v[i,1]]+q[i,0]+q[i,1])
then f[j]:=f[j-v[i,0]-v[i,1]]+v[i,0]*q[i,0]+q[i,1];
if v[i,2]>0then if(j-v[i,0]-v[i,2]>0)and(f[j]<f[j-v[i,0]-v[i,2]]+q[i,0]+q[i,2])
then f[j]:=f[j-v[i,0]-v[i,2]]+q[i,0]+q[i,2];
if (v[i,1]>0)and(v[i,2]>0)then if(j-v[i,0]-v[i,1]-v[i,2]>0)and(f[j]<f[j-v[i,0]-v[i,1]-v[i,2]]+q[i,0]+q[i,1]+q[i,2])
then f[j]:=f[j-v[i,0]-v[i,1]-v[i,2]]+q[i,0]+q[i,1]+q[i,2];
end;
writeln(f[n]*10);
end.