真的跪了....分组背包....这这这究竟为什么始终挂掉56两个点?提交N遍后对此实在是无力了..
求大牛点拨 多谢
T_T
状态: Unaccepted
测评机: Xeost[5]
得分: 80分
提交日期: 2012-11-8 10:54:00
有效耗时: 1577毫秒
测试结果1: 通过本测试点|有效耗时250ms
测试结果2: 通过本测试点|有效耗时219ms
测试结果3: 通过本测试点|有效耗时172ms
测试结果4: 通过本测试点|有效耗时171ms
测试结果5: 测试结果错误.错误结果为:25900
正确结果应为:26400
测试结果6: 测试结果错误.错误结果为:35300
正确结果应为:36400
测试结果7: 通过本测试点|有效耗时188ms
测试结果8: 通过本测试点|有效耗时187ms
测试结果9: 通过本测试点|有效耗时203ms
测试结果10: 通过本测试点|有效耗时187ms
提交代码: view sourceprint?
program P6;
type
no=record
v:integer;
w:longint;
end;
var
q,m,n,i,j,w1,v1,t,k:integer;
a:array[-5..65,1..4]of no;
b,c:array[-5..65]of integer;
f:array[-5..32005]of longint;
function max(x:integer):integer;
var
i,j:integer;
begin
j:=0;
for i:=1 to 4 do
if a[x,i].v>j then j:=a[x,i].v;
exit(j);
end;
begin
readln(n,m);
j:=0;
for i:=1 to m do
begin
read(v1,w1,q);
if q=0 then
begin
inc(j);
b[i]:=j;
a[j,1].v:=v1;
a[j,1].w:=v1*w1; c[j]:=1;
end else
begin
t:=b[q];
k:=2; c[t]:=2;
if a[t,k].w<>0 then k:=3;
a[t,k].v:=v1+a[t,1].v;
a[t,k].w:=w1*v1+a[t,1].w;
if k=3 then
begin
a[t,4].v:=a[t,2].v+a[t,3].v-a[t,1].v;
a[t,4].w:=a[t,2].w+a[t,3].w-a[t,1].w;
c[t]:=4;
end;
end;
end; //初始化合并物品
t:=j;
for i:=1 to t do
//分组
for j:=n downto max(i) do
for k:=1 to c[i] do
begin
if f[j-a[i,k].v]+a[i,k].w>f[j]
then f[j]:=f[j-a[i,k].v]+a[i,k].w;
end;
writeln(f[n]);
end.