- 公司聚会
- 2009-10-24 16:15:44 @
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 条评论
-
庆卿清情 LV 8 @ 2009-10-24 18:05:37
up
那位大牛帮帮忙啊
改了一天了
吐了.....
- 1