金明的预算方案[NOIP2006提高组 第二题]

———————————————————————————————————————

var

n,m:longint;

i,j:longint;

v,p,q:array[1..60]of longint;

f:array[1..32000,1..60]of longint;

b:array[0..60]of boolean;

function max(a,b:longint):longint;

begin

if a>b then exit(a) else exit(b);

end;

begin

assign(input,'budget.in');

assign(output,'budget.out');

reset(input);

rewrite(output);

readln(n,m);{读入数据}

for i:=1 to m do

readln(v[i],p[i],q[i]);{end}

fillchar(f,sizeof(f),0);

fillchar(b,sizeof(b),false);

b[0]:=true;{初始化}

for i:=1 to n do {DP}

for j:=1 to m do

if (b[q[j]])and(i>v[j]) then

begin

b[j]:=true;

f[i,j]:=max(f[i,j-1] , f[i-v[j],j-1]+v[j]*p[j]);

end

else f[i,j]:=f[i,j-1];{end}

writeln(f[n,m]);

close(output);

close(input);

end.