编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

ＯＲＺ．．．．．．．．．．．

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

过了

[blue]

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

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

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

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

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

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

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

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

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

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

倒背包做了大号，

今天用小号做了treedp

猥琐，吧！！！

注意有c[i]为0情况，

没一次AC

猥琐，吧！！！

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

汗`\ 慢了

开始没看题解

很猥琐的去转成二叉树!!!

然后用记忆化编了个 treedp!!!

结果慢了!!!

切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切切记！要downto！

数组f表示i点向下用j的花费和得到的最大值。

初始f:=0;

然后从叶子向跟拓展并不断更新父接点。

附上代码：

program vijos;

var h,i,j,k,hh,n,m,max,t:longint;

b:array[1..1024] of boolean;

c,d,l,w:array[1..1024] of integer;

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

begin

readln(n,m);

fillchar(l,sizeof(l),0);

for i:=2 to n do

begin

read(k);

d[i]:=k;

inc(l[k]);

end;

readln;

for i:=1 to n do

read(w[i]);

readln;

for i:=1 to n do

read(c[i]);

for i:=1 to n do

begin

f:=0;

for j:=1 to m do

f:=-maxlongint;

end;

fillchar(b,sizeof(b),true);

b[1]:=false;

while true do

begin

for i:=2 to n do

if b[i] and (l[i]=0) then

begin

b[i]:=false;

t:=d[i];

dec(l[t]);

if (w[i]f) then

f:=c[i];

for hh:=m downto 0 do

for h:=0 to hh do

begin

j:=hh-h;

if (f-maxlongint)and(f[t,j]-maxlongint)and(f+f[t,j]>f[t,j+h]) then

f[t,j+h]:=f+f[t,j];

end;

end;

if l[1]=0 then break;

end;

if (w[1]f[1,w[1]]) then

f[1,w[1]]:=c[1];

max:=-maxlongint;

for i:=0 to m do

if f[1,i]>max then

max:=f[1,i];

write(max);

end.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

treeDP

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

treeDP

DP题。

关键代码：

for i:=n downto 2 do

begin

for j:=c[i] to m do

if e[i]>f then

f:=e[i];

for j:=m downto 0 do {这里一定要倒着}

for k:=0 to j do

if f[p[i],j]

编译通过...

├ 测试数据 01：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 02：答案错误...　├ 标准行输出

　├ 错误行输出

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

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

├ 测试数据 05：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 06：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 07：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 08：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 09：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 10：答案错误...　├ 标准行输出

　├ 错误行输出

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

Unaccepted 有效得分：20 有效耗时：0ms

var

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

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

l,c,e:array[0..1200]of integer;

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

begin

if a

j123

谁能讲讲算法，别老把ac结果贴出来

treedp//

#include

struct aa {long s,b;}tree[2000];

long c[2000],e[2000],n,dp[1025][200],m,t;

void lian(long a,long b)

{

if (tree[a].s==0) {tree[a].s=b; return;}

a=tree[a].s;

while (tree[a].b!=0) a=tree[a].b;

tree[a].b=b;

}

void du()

{

long i,j;

long a,b;

memset(dp,128,sizeof(dp)); memset(tree,0,sizeof(tree));

t=dp[0][0];

for (i=0; i

记忆化treedp,竟然t了2个dian

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

同意...因为上司的编号都小与自己的编号,所以可以用倒退型的0/1背包

状态转移方程：

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：答案正确... 41ms

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

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

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

第一次 数组大小开小了

第二次 数组元素开小了

第三次 AC……

郁闷……………………

f表示以i为根花j元的最大快乐度：

f=max( f[b[i],j-c[i]]+e[i] , f[s[i],k],f[b[i],j-k] ); (0

华丽的树形DP莫名的WA了2个点。。。。。。

逼我换背包。。。。。。

开始读错了题目 以为和那个经典问题一样 是不能请某职员和其直接上司 感觉加了一维好bt啊 原来。。。。。。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

看色董吉写的。。。要从后往前推，否则会有后效性，一个结点用几次的情况。。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

记忆化搜索的树形DP。。。。。。

居然有Ci=0的情况，不考虑只有50分