program lq;
const
inf='budget.in';
ouf='budget.out';
var
v,n,i,j,k,l,c0:longint;
c,w:array[0..60,1..3] of longint;
b:array[0..60] of byte;
f:array[0..60,0..3200] of longint;
begin
assign(input,inf);reset(input);
assign(output,ouf);rewrite(output);
readln(v,n);
v:=v div 10;
fillbyte(b,sizeof(b),1);
for i:=1 to n do begin
readln(j,k,l);
if l=0 then begin
inc(c0);
c[c0,1]:=j div 10;
w[c0,1]:=k;
end
else begin
inc(b[l]);
c[l,b[l]]:=j div 10;
w[l,b[l]]:=k;
end;
end;
close(input);
for i:=1 to c0 do
for j:=0 to v do begin
f:=f;
if ((j>=c) and (f < (f[i-1,j-c]+w*c))) then
f:=(f[i-1,j-c]+w*c);
if ((j>=c+c) and
(f < (f[i-1,j-c-c]+w*c+w*c))) then
f:=(f[i-1,j-c-c]+w*c+w*c);
if ((j>=c+c) and
(f < (f[i-1,j-c-c]+w*c+w*c))) then
f:=(f[i-1,j-c-c]+w*c+w*c);
if ((j>=c+c+c) and
(f < (f[i-1,j-c-c-c]+w*c+w*c+w*c))) then
f:=(f[i-1,j-c-c-c]+w*c+w*c+w*c);
end;
writeln(f[c0,v]*10);
close(output);
end.
3 条评论
-
lzqqqqq LV 4 @ 2014-03-30 14:21:06
shaq吧
-
@ 2013-10-06 10:53:15
var
val,exp:array[1..60,0..2]of longint;
pre:array[1..60]of longint;
f:array[0..60,0..3200]of longint;
n,s:integer;procedure init;
var i,m,v,p,q,k,j:longint;
begin
fillchar(f,sizeof(f),0);
fillchar(val,sizeof(val),0);
fillchar(exp,sizeof(exp),0);
fillchar(pre,sizeof(pre),0);
readln(n,m);
n:=n div 10; s:=0;
for i:=1 to m do
begin
readln(v,p,q);
v:=v div 10;
if q=0 then
begin
inc(s);
pre[s]:=i;
val[s,0]:=v;
exp[s,0]:=p;
end else
begin
for j:=1 to s do if pre[j]=q then break;
if val[j,1]=0 then
begin val[j,1]:=v; exp[j,1]:=p; end else
begin val[j,2]:=v; exp[j,2]:=p; end;
end;
end;
end;function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;procedure dp;
var i,j,k:longint;
begin
for i:=1 to s do
for j:=0 to n do
begin
f[i,j]:=f[i-1,j];
if j>=val[i,0] then f[i,j]:=max(f[i,j],f[i-1,j-val[i,0]]+val[i,0]*exp[i,0]);
if j>=val[i,0]+val[i,1] then f[i,j]:=max(f[i,j],f[i-1,j-val[i,0]-val[i,1]]+val[i,0]*exp[i,0]+val[i,1]*exp[i,1]);
if j>=val[i,0]+val[i,2] then f[i,j]:=max(f[i,j],f[i-1,j-val[i,0]-val[i,2]]+val[i,0]*exp[i,0]+val[i,2]*exp[i,2]);
if j>=val[i,0]+val[i,1]+val[i,2] then f[i,j]:=max(f[i,j],f[i-1,j-val[i,0]-val[i,1]-val[i,2]]+val[i,0]*exp[i,0]+val[i,1]*exp[i,1]+val[i,2]*exp[i,2]);
end;
writeln(f[s,n]*10);
end;begin
init;
dp;
end. -
@ 2010-07-22 19:41:22
可能没有主件只有附件
- 1
