讨论 / 一点感想
zhhyoi 2009-11-16 05:04:00
点我顶贴 收藏 删除
有个细节

q是第几件物品的编号,而不是第几个主件的编号

大家千万不要累加主件

program zhhy;

type arr=record

z:longint;

f1:longint;

f2:longint;

end;

var ans,n,m,i,j,p,q,vv:longint;

f:array[0..320000]of longint;

v,w:array[0..100]of arr;

function max(x,y:longint):longint;

begin

if x>y then exit(x)

else exit(y);

end;

begin

readln(m,n);

j:=1;

fillchar(w,sizeof(w),0);

for i:=1 to n do

begin

readln(vv,p,q);

if q=0 then begin w[j].z:=vv; v[j].z:=vv*p; inc(j);end

else if w[q].f1=0 then begin

w[q].f1:=vv;

v[q].f1:=vv*p;

end

else begin

w[q].f2:=vv;

v[q].f2:=vv*p;

end;

end;

n:=j-1;

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

for i:=1 to n do

for j:=m downto 0 do

begin

if j-w[i].z>=0 then

f[j]:=max(f[j],f[j-w[i].z]+v[i].z);

if j-w[i].z-w[i].f1>=0 then

f[j]:=max(f[j],f[j-w[i].z-w[i].f1]+v[i].z+v[i].f1);

if j-w[i].z-w[i].f2>=0 then

f[j]:=max(f[j],f[j-w[i].z-w[i].f2]+v[i].z+v[i].f2);

if j-w[i].z-w[i].f1-w[i].f2>=0 then

f[j]:=max(f[j],f[j-w[i].z-w[i].f1-w[i].f2]+v[i].z+v[i].f1+v[i].f2);

ans:=max(ans,f[j]);

end;

writeln(ans);

readln;

readln;

end.

累加主件 60分

program zhhy;

type arr=record

z:longint;

f1:longint;

f2:longint;

end;

var ans,n,m,i,j,p,vv:longint;

q:array[0..100]of integer;

f:array[0..320000]of longint;

v,w:array[0..100]of arr;

function max(x,y:longint):longint;

begin

if x>y then exit(x)

else exit(y);

end;

begin

readln(m,n);

fillchar(w,sizeof(w),0);

for i:=1 to n do

begin

readln(vv,p,q[i]);

if q[i]=0 then begin w[i].z:=vv; v[i].z:=vv*p; end

else if w[q[i]].f1=0 then begin

w[q[i]].f1:=vv;

v[q[i]].f1:=vv*p;

end

else begin

w[q[i]].f2:=vv;

v[q[i]].f2:=vv*p;

end;

end;

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

for i:=1 to n do

if q[i]=0 then

for j:=m downto 0 do

begin

if j-w[i].z>=0 then

f[j]:=max(f[j],f[j-w[i].z]+v[i].z);

if j-w[i].z-w[i].f1>=0 then

f[j]:=max(f[j],f[j-w[i].z-w[i].f1]+v[i].z+v[i].f1);

if j-w[i].z-w[i].f2>=0 then

f[j]:=max(f[j],f[j-w[i].z-w[i].f2]+v[i].z+v[i].f2);

if j-w[i].z-w[i].f1-w[i].f2>=0 then

f[j]:=max(f[j],f[j-w[i].z-w[i].f1-w[i].f2]+v[i].z+v[i].f1+v[i].f2);

ans:=max(ans,f[j]);

end;

writeln(ans);

end.

改成第N个物品编号100

#1 cmk1111@2009-11-16 05:04:00
回复 删除
感谢LZ提醒

不然我就要在此题目上submit20+次了

查看更多回复
提交回复