编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 9ms

├ 测试数据 07：答案正确... 25ms

├ 测试数据 08：答案正确... 25ms

├ 测试数据 09：答案正确... 25ms

├ 测试数据 10：答案正确... 25ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：109ms

丑陋的时间~~~

做了一段时间的BFS，写完这题，老觉得………………代码很短！！！

哦。。。

var

n,m,i,j,k:longint;

p,c,e:array[0..1200]of longint;

f:array[0..1200,0..1200]of longint;

begin

readln(n,m);

for i:=2 to n do read(p[i]);

for i:=1 to n do read(c[i]);

for i:=1 to n do read(e[i]);

for i:=n downto 1 do

begin

for j:=m downto c[i] do if f

倒退型的01背包

状态转移方程：

f[p[i],j]:=max(f[p[i],j],f[p[i],j-k]+f)

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

DP开了老大的数组才过。。0..1200,0..1200

奇奇怪怪。。。

同样一个程序交了4遍都不过。。。最后把范围开到[1..2000，0..200]就过了。。

注意存在花费0价值大于0的情况！害人啊！！！

感谢楼下某牛提醒···

少了这个 树形dp 只拿50啊

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 103ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 88ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：191ms

TreeDP.

注意循环的顺序，弄不好调半天。

我写的比较原始，但是有我的一些思考。

调半天弄不出来很恶心的，贴代码吧。

for(i=c[k];i=0;i--)

for(j=0;j

26行

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

感谢K103701告诉我这题怎么做~~

一开始没注意到子节点的编号一定会比父节点大，根据这个特殊的性质，就可以进行0，1背包，f表示以i为根节点花费j元的最大值

倒着DP,可以用子节点来跟新父节点的值，也就是说知道f的值，可以更新出f[p[i],Y]的值，当一个节点的子节点全部求出的时候那么那个节点的最优值也就求出了，第一次做这样的题，我还转的半天二叉树~~

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

program Project1;

var son:array[0..1025,0..1025]of longint;

e,c,id,f:array[0..1025]of longint;

i,m,n,fa,q:longint;

function max(a,b:longint):longint;

begin

max:=a;

if b>max then max:=b;

end;

procedure make(point:longint);

var j,k:longint;

g:array[0..1025]of longint;

begin

if id[point]=0 then

begin

if c[point]=0 then

for j:=1 to m do f[j]:=max(f[j],f[j]+e[point])

else

for j:=m downto c[point] do

begin

if f[j-c[point]]+e[point]>f[j] then f[j]:=f[j-c[point]]+e[point];

end;

exit;

end;

g:=f;

if c[point]=0 then

for j:=1 to m do g[j]:=max(g[j],g[j]+e[point])

else

for j:=m downto c[point] do

begin

if g[j-c[point]]+e[point]>g[j] then g[j]:=g[j-c[point]]+e[point];

end;

for k:=1 to id[point] do

make(son[point,k]);

for j:=1 to m do

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

end;

begin

read(n,m);

for i:=2 to n do

begin

read(fa);

inc(id[fa]);

son[fa,id[fa]]:=i;

end;

for i:=1 to n do read(c[i]);

for i:=1 to n do read(e[i]);

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

make(1);

fa:=0;

for i:=1 to m do if f[i]>fa then fa:=f[i];

writeln(fa);

end.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 9ms //郁闷

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：9ms

一共25行 从后往前DP 在处理I之前f的所有值都是指I不参加的

然后f:=max(f,e[i]);

f[fa[i],j]:=max(f[fa[i],j],f[fa[i],j-k]+f])

更新I 及fa[i]

第100人~~

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 244ms

├ 测试数据 07：答案正确... 275ms

├ 测试数据 08：答案正确... 322ms

├ 测试数据 09：答案正确... 291ms

├ 测试数据 10：答案正确... 275ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1407ms

好慢……

终于过了。。。

我连交了10次才AC。。。降了2点正确率啊。。。

就因为没有单独做 F[P，J]：=F[P，J]+F；再背包。。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 25ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 9ms

├ 测试数据 10：答案正确... 25ms

多叉转二叉啊，数据结构真强大啊，后悔学得不怎么好啊，以前以为学二叉就是为了初赛啊，误解多么大啊。纪念一下吧。

f:=max(f,e[i]);

f[p[i],j]:=max(f[p[i],k]+f,f[p[i],j]);

(p[i]为i的上司)

注意循环顺序，能让此方程满足题意，即不同时取上司与下属，也不重复取

程序不超过30行

M 到底有多大？？？？？

终于搞懂treedp了

beibao