kingofpupil @ 2018-07-12 09:44:11
uses math; var n,m,a,b,c,i,j,k,l:longint; v,w:Array[0..100,0..3] of longint; f:array[0..33000] of longint; no:array[0..100] of byte; begin readln(n,m); for i:=1 to m do begin readln(a,b,c); b:=b*a; if c=0 then begin v[i,0]:=b;w[i,0]:=a;end else begin inc(no[c]); v[c,no[c]]:=b; w[c,no[c]]:=a; end; end; for i:=1 to m do begin if w[i,0]=0 then continue; for j:=n downto w[i,0] do begin f[j]:=max(f[j],f[j-w[i,0]]+v[i,0]); if j-w[i,0]-w[i,1]>0 then f[j]:=max(f[j],f[j-w[i,0]-w[i,1]]+v[i,0]+v[i,1]); if j-w[i,0]-w[i,2]>0 then f[j]:=max(f[j],f[j-w[i,0]-w[i,2]]+v[i,0]+v[i,2]); if j-w[i,0]-w[i,1]-w[i,2]>0 then f[j]:=max(f[j],f[j-w[i,0]-w[i,1]-w[i,2]]+v[i,0]+v[i,1]+v[i,2]); end; end; writeln(f[n]); end.
by __Hacheylight__ @ 2018-07-12 10:01:04
// luogu-judger-enable-o2
uses math ;
var f1,f2,v,p,c:array[0..32000] of longint ;
f:array[0..100,0..32000] of longint ;
m,n,k,i,j:longint ;
begin
readln(m,n) ;
m:=m div 10 ;
for i:=1 to n do
begin
read(v[i],p[i],k) ;
v[i]:=v[i] div 10 ;
if k>0 then
if f1[k]>0 then f2[k]:=i
else f1[k]:=i
else c[i]:=1 ;
end;
for i:=1 to n do
for j:=1 to m do
begin
f[i,j]:=f[i-1,j] ;
if c[i]=0 then continue ;
if j>=v[i] then
f[i,j]:=max(f[i][j],f[i-1,j-v[i]]+v[i]*p[i]) ;
if (f1[i]>0) and (j>=v[i]+v[f1[i]]) then
f[i,j]:=max(f[i,j],f[i-1,j-v[i]-v[f1[i]]]+v[i]*p[i]+v[f1[i]]*p[f1[i]]) ;
if (f2[i]>0) and (j>=v[i]+v[f2[i]]) then
f[i,j]:=max(f[i,j],f[i-1,j-v[i]-v[f2[i]]]+v[i]*p[i]+v[f2[i]]*p[f2[i]]) ;
if (f1[i]>0) and (f2[i]>0) and (j>=v[i]+v[f1[i]]+v[f2[i]]) then
f[i,j]:=max(f[i,j],f[i-1,j-v[i]-v[f1[i]]-v[f2[i]]]+v[i]*p[i]+v[f1[i]]*p[f1[i]]+v[f2[i]]*p[f2[i]]) ;
end;
writeln(f[n,m]*10) ;
end.@jiangzijin