dangertrip 2010-08-05 05:59:00
点我顶贴
收藏
删除
var
a:array[0..32000] of longint;
c,v,d:array[1..60] of longint;
e,f:array[0..60,0..60] of longint;
i,j,k,l,m,n,x,y:longint;
function max(x,y:longint):longint;
begin
if x>y then exit(x) else exit(y);
end;
begin
fillchar(a,sizeof(a),0);
fillchar(e,sizeof(e),0);
readln(m,n);
for i:=1 to n do
begin
readln(v[i],c[i],d[i]);
if d[i]=0 then
begin
e[i,0]:=1;
e[i,1]:=v[i];
f[i,1]:=v[i]*c[i];
end;
end;
for i:=1 to n do
if d[i]>0 then
begin
k:=d[i];x:=e[k,0];
for j:=1 to x do
begin
inc(e[k,0]);
e[k,e[k,0]]:=e[k,j]+v[k];
f[k,e[k,0]]:=f[k,j]+v[k]*c[k];
end;
end;
for i:=1 to n do
if e[i,0]>0 then
for j:=m downto 1 do
for k:=1 to e[i,0] do
if j>=e[i,k] then
a[j]:=max(a[j],a[j-e[i,k]]+f[i,k]);
writeln(a[m]);
end.