4种状态,每种要写100多个字符
但只有80分,
运行错误|普通保护错误 这是什么东西
type
cc=record
val,im,fj,q,next:longint;
end;
var
a:array[0..100,0..2]of cc;
f:array[0..32000]of longint;
i,j,k,m,n,v,p,q,tot:Longint;
function max(a,b:Longint):Longint;
begin
if a>b then exit(a)else
exit(b);
end;
begin
read(n,m);
tot:=0;
for i:=1to m do
begin
read(a[i,0].val,a[i,0].im,a[i,0].q);
if a[i,0].q<>0 then
begin
q:=a[i,0].q;
inc(a[q,0].fj);
v:=a[q,0].fj;
a[q,v].next:=i;
end;
end;
for i:=1 to m do
if a[i,0].q=0 then
for j:=n downto a[i,0].val do
begin
f[j]:=max(f[j],f[j-a[i,0].val]+a[i,0].val*a[i,0].im);
if (a[i,0].fj>=1)and(j-a[i,0].val-a[a[i,1].next,0].val>=0) then
f[j]:=max(f[j],f[j-a[i,0].val-a[a[i,1].next,0].val]+a[i,0].val*a[i,0].im+a[a[i,1].next,0].val*a[a[i,1].next,0].im);
if a[i,0].fj=2 then
begin
if (j-a[i,0].val-a[a[i,2].next,0].val>=0)
then
f[j]:=max(f[j],f[j-a[i,0].val-a[a[i,2].next,0].val]+a[i,0].val*a[i,0].im+a[a[i,2].next,0].val*a[a[i,2].next,0].im);
if (j-a[i,0].val-a[a[i,2].next,0].val-a[a[i,1].next,0].val>=0)then
begin
q:=a[i,2].next;p:=a[i,1].next;
f[j]:=max(f[j],f[j-a[i,0].val-a[q,0].val-a[p,0].val]+a[i,0].val*a[i,0].im+a[q,0].val*a[q,0].im+a[p,0].val*a[p,0].im);
end;
end;
end;
for i:=n downto 1 do
begin
if a[i,0].q=0 then
begin
writeln(f[i]);
exit;
end;
end;
end.
var
p,v:array[1..10000,0..2]of longint;
f:array[0..32000]of longint;
i,j,k,m,n,a,b,c,v0,v1,v2,p0,p1,p2:longint;
begin
assign(input,'e:/1.in');
reset(input);
read(n,m);
n:=n div 10;
for i:=1 to m do
begin
read(a,b,c);
if c=0 then c:=i;
for j:=0 to 2 do
if v[c,j]=0 then
begin
v[c,j]:=a div 10;
p[c,j]:=v[c,j]*b;
break;
end;
end;
for i:=1 to m do
if v[i,0]<>0 then
begin
v0:=v[i,0];
v1:=v[i,1];
v2:=v[i,2];
p0:=p[i,0];
p1:=p[i,1];
p2:=p[i,2];
for j:=n downto 0 do
begin
if (j>=v0)and(f[j]<f[j-v0]+v0*p0)then
f[j]:=f[j-v0]+p0;
if (j>=v0+v1)and(f[j]<f[j-v0-v1]+v0*p0+v1*p1)then
f[j]:=f[j-v0-v1]+p0+p1;
if (j>=v0+v2)and(f[j]<f[j-v0-v2]+v0*p0+v2*p2)then
f[j]:=f[j-v0-v2]+p0+p2;
if (j>=v0+v1+v2)and(f[j]<f[j-v0-v1-v2]+v0*p0+v1*p1+v2*p2)then
f[j]:=f[j-v0-v1-v2]+p0+p1+p2;
end;
end;
writeln(f[n]*10);
end.
据说贪心的最高境界是淘汰DP看来...
其实这个题用背包很好解的...
这种贪心最好还是不要写,一不留神就少考虑几种情况,并且代码会很长。十分不利于检查。
我是在只有束手无策的情况(这种情况很多...)下才会如此...