讨论 / 大牛来一下!!!
RP 2009-07-06 19:25:00
点我顶贴 收藏 删除
题号:493

为什么不对??

请各位大牛指点一下??

源程序:

program lj;

var

a:array[1..100,-1000..1000,1..2] of integer;

b:array[1..100,1..3]of integer;

i,j,k,d,h,g:integer;

procedure swap(var x,y:integer);

var

t:integer;

begin

t:=x;x:=y;y:=t;

end;

procedure kp(s,t:integer);

var

i,j,x:integer;

begin

i:=s;j:=t;x:=b[trunc((i+j)/2),1];

repeat

while b[i,1]<x do inc(i);

while b[j,1]>x do dec(j);

if i<=j then begin swap(b[i,1],b[j,1]); swap(b[i,2],b[j,2]); swap(b[i,3],b[j,3]); inc(i); dec(d); end;

until (i>j);

if (j>s) then kp(s,j);

if (i<t) then kp(i,t);

end;

begin

read(h,g);

for i:=1 to g do read(b[i,1],b[i,2],b[i,3]);

kp(1,g);

a[1,0,1]:=1; a[1,0,2]:=10+b[1,2];

a[1,b[1,3],1]:=1;a[1,b[1,3],2]:=10;

if b[1,1]>10 then write(10)

else if b[1,3]>h then write(b[1,1])

else for i:=2 to g do begin

k:=0;

d:=0;

for j:=0 to h do begin

if (a[i-1,j,1]=1) and (a[i-1,j,2]>=b[i,1]) then begin a[i,j,1]:=1; a[i,j,2]:=a[i-1,j,2]+b[i,2]; k:=1; if j>=h then d:=1; end;

if (a[i-1,j-b[i,3],1]=1) and (a[i-1,j-b[i,3],2]>=b[i,1]) then if a[i-1,j-b[i,3],2]>a[i,j,2] then begin a[i,j,1]:=1; a[i,j,2]:=a[i-1,j-b[i,3],2]; k:=1; if j>=h then d:=1; end;

end;

if k=0 then begin write(a[i-1,0,2]); break; end;

if d=1 then begin write(b[i,1]); break; end;

end;

end.

--------------------------------------------------

我用的是01背包,结果显示栈溢出。

#1 Mato完整版@2009-07-06 19:25:00
回复 删除
提示:F[i, j]表示在第i个垃圾扔下来之后,有j点能量能堆的最高的高度。
查看更多回复
提交回复