为何tle?

program v1418;

type

tree=record

l,r:longint;

end;

var f:array[0..1024,0..109]of longint;

t:array[1..1024]of tree;

w,v:array[1..1024]of longint;

i,n,m,x:longint;

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

begin

if x>y then

exit(x) else exit(y);

end;

procedure dp(i,j:longint);

var k:longint;

begin

if i*j=0 then exit;

if f0 then exit;

if (j>=v[i])and(w[i]>0) then

begin

dp(t[i].r,j-v[i]);

f:=f[t[i].r,j-v[i]]+w[i];

end;

for k:=0 to j do

begin

dp(t[i].l,k);

dp(t[i].r,j-k);

f:=max(f,f[t[i].l,k]+f[t[i].r,j-k]);

end;

end;

begin

readln(n,m);

for i:=2 to n do

begin

read(x);

if t[x].l=0 then

t[x].l:=i else

begin

x:=t[x].l;

while t[x].r0 do

x:=t[x].r;

t[x].r:=i;

end;

end;

for i:=1 to n do

read(v[i]);

for i:=1 to n do

read(w[i]);

dp(1,m);

writeln(f[1,m]);

end.

应该是标准的treedp吧,为什么6个点超时呢

1 条评论

  • @ 2009-10-24 18:05:37

    up

    那位大牛帮帮忙啊

    改了一天了

    吐了.....

  • 1

信息

ID
1418
难度
5
分类
动态规划 | 树形DP 点击显示
标签
(无)
递交数
1013
已通过
345
通过率
34%
被复制
3
上传者