方程很简单，就是被根结点为0卡了一次：

改成两句就AC了......

tree[0].right:=tree[0].left;

tree[0].left:=0;

很惊叹通过率为什么这么高。。。

我一做这题就一直有一种心理暗示：这题很难。做了才觉得不是很难。

首先就是多叉转二叉，兄弟存一支，儿子存一支。

然后要拓扑排序，确定动归顺序。

最后动归：f表示以i为根的子数取j个课的最大价值，方程就看下面的牛们吧！

数据好象比较弱

编译通过...

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

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

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

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

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

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

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

DP+前序遍利所有节点

注意要剪枝

var i,n,m,k:integer;

a:array[0..300] of byte;

l:array[0..300,1..300] of integer;

f:array[0..300,0..300] of integer;

r:array[0..300] of integer;

t:array[0..300] of integer;

procedure fdq(k:integer);

var i,j,s,min,max:integer;

begin

t[k]:=1;

for i:=1 to r[k] do begin

fdq(l[k,i]);

inc(t[k],t[l[k,i]]);

end;

f[k,1]:=a[k];

for i:=1 to r[k] do

for s:=t[k]+t[l[k,i]] downto 2 do begin

if s-t[k]>1 then max:=s-t[k] else max:=1;

if s-10) and (f[l[k,i],j]+f[k,s-j]>f[k,s])

then f[k,s]:=f[l[k,i],j]+f[k,s-j];

end;

end;

begin

readln(n,m);

fillchar(r,sizeof(r),0);

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

for i:=1 to n do begin

readln(k,a[i]);

inc(r[k]);

l[k,r[k]]:=i;

end;

a[0]:=1;

fdq(0);

writeln(f[0,m+1]-1);

end.

神奇的通过人数 VJ炒代码现象太严重了。。

int dp(int v, int s)//以v为根的子树选了s门课的最大学分

{

if (DP[v] != -1) return DP[v];

if (s == 0) return DP[v] = 0;

if (T[v].L == -1 && T[v].R == -1) return DP[v] = T[v].V;

if (T[v].L != -1 && T[v].R == -1) return DP[v] = T[v].V + dp(T[v].L, s - 1);

if (T[v].L == -1 && T[v].R != -1) return DP[v] = Max(T[v].V + dp(T[v].R, s - 1), dp(T[v].R, s));

else

{

int Res = dp(T[v].R, s);

for (int k = 1; k Res)

Res = T[v].V + dp(T[v].L, k - 1) + dp(T[v].R, s - k);

return DP[v] = Res;

}

}感觉树状数组 想清楚了 思路异常清晰

555555555555数组开到1000才能AC，不然只能60分。

编译通过...

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

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

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

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

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

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

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

#include "stdio.h"

typedef struct _node

{

int l,r;

int value;

}node;

int m,n;

int i,j;

int a,b; // temporary.

node c[ 1000];

int f[1000][1000];

int treedp( int nd, int amount)

{

int max;

int temp;

int i;

if( f[ nd][amount] > 0) return 1;

if( nd == -1) return 1;

treedp( c[ nd].r , amount);

max = f[ c[nd].r][amount];

for( i = 1; i max ) max = temp;

}

f[ nd][ amount] = max;

}

int main()

{

//FILE *fp = fopen( "D:/temp.txt", "r");

fscanf( stdin, "%d%d", &n, &m);

for( i = 0; i

虽然就是个背包.....

我觉得这题也挺难的

啊!我竟然!没做出来...额...不会树归。.

递归没回值 wa了一次

记忆化搜索忘了返回值 wa了n次

太汗了 = =

下次编一定要细心

我的方法有点恶心。。。树形DP+记忆化搜索，2个状态转移方程相互调用。。。

没有转二叉树

全部0ms

57行代码

竟然有O(NM)的算法

而且才15行、、、

编译通过...

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

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

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

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

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

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

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

var

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

a,b,l,r:Array[0..1000]of longint;

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

g:array[0..1000]of boolean;

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

begin

if x>y

then max:=x

else max:=y;

end;

procedure li(x:longint);

var

i:longint;

begin

for i:=1 to n do

if (a[i]=x)and(g[i])and(ix)

then begin

g[i]:=false;

l[x]:=i;

li(i);

break;

end;

for i:=1 to n do

if (a[i]=a[x])and(ix)and(g[i])

then begin

g[i]:=false;

r[x]:=i;

li(i);

break;

end;

end;

function ke(i,v:longint):longint;

var

k:longint;

begin

if (l[i]=0)and(r[i]=0)

then if v>=1

then exit(b[i])

else exit(0);

if f0

then exit(f);

f:=ke(r[i],v);

for k:=v-1 downto 0 do

f:=max(f,ke(l[i],k)+ke(r[i],v-1-k)+b[i]);

exit(f);

end;

begin

readln(n,m);

for i:=1 to n do

readln(a[i],b[i]);

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

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

fillchar(r,sizeof(r),0);

fillchar(g,sizeof(g),true);

for i:=1 to n do

if a[i]=0

then begin

g[i]:=false;

li(i);

break;

end;

write(ke(i,m));

end.

记忆化

树型背包

编译通过...

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

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

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

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

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

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

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

大家都用树形做吗？？

我用超厌的预处理和01背包

（被众人[strong]ia[/Strong]飞）

编译通过...

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

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

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

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

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

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

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

正在研究此题

TREE DP

很好很强大

提供一个初学者建树方法：

if tree[a[i]].l为空，则赋值b[i]

else

while(1)

{

if tree[a[i]].r为空，则赋值b[i];break;

else a[i]=tree[a[i]].r;

}

编译通过...

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

一直在琢摸n叉转2叉是否等价的问题，

看了题解终于豁然开朗

program lx;

var i,j,k,l,m,n,p,q:longint;

a:array[-1..400,0..2] of longint;

b:array[-1..400,-1..400] of longint;

f:array[-1..400] of longint;

procedure treedp(x,y:longint);

var i,j,k:longint;

begin

if b[x,y]>=0 then exit;

treedp(a[x,2],y);j:=b[a[x,2],y];

for k:=1 to y do

begin

treedp(a[x,1],k-1);

treedp(a[x,2],y-k);

i:=b[a[x,1],k-1]+a[x,0]+b[a[x,2],y-k];

if i>j then j:=i;

end;

b[x,y]:=j;

end;

begin

readln(n,m);

for i:=0 to n do begin a:=-1;a:=-1;a:=-1;end;

for i:=1 to n do

begin

readln(p,q);a:=q;

if f[p]=0 then begin a[p,1]:=i;end

else a[f[p],2]:=i;

f[p]:=i;

end;

for i:=-1 to n do

for j:=0 to m do if (i=-1)or(j=0) then b:=0 else b:=-1;

treedp(a[0,1],m);

writeln(b[a[0,1],m]);

end.

树形DP

DP方程：

f:=max{f+f[l.rc,j-k]};

我的详细解释：

http://hi.baidu.com/stillchou/blog/item/8fce7d0089e8b5097aec2c63.html

program v1180;

type treetype=record

lch,rch,fa:longint;

end;

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

tree:array[0..300]of treetype;

w:array[0..300]of longint;

n,m,i,j,k,t,st,r:longint;

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

begin

max:=a;

if max