codevs 1378选课树形DP

74 阅读 0 评论 49 点赞

我是靠谱客的博主漂亮短靴，最近开发中收集的这篇文章主要介绍codevs 1378选课树形DP，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 int N,M,tl[303],tr[303],f[303][303],num[303],con[303];
 6 void insect(int fa,int now)
 7 {
 8
if (tl[fa]==0)
 9
{tl[fa]=now;}
10
else
11 
{
12
int i=tl[fa];
13
while (tr[i]!=0) i=tr[i];
14
tr[i]=now;
15 
}
16 }
17 void dfs(int x)
18 {
19
if (tr[x]!=0) dfs(tr[x]);
20
if (tl[x]!=0) dfs(tl[x]);
21
con[x]=con[tr[x]]+con[tl[x]]+1;
22
int i,j;
23
f[x][1]=num[x];
24
for (i=0;i<=con[tr[x]];++i)
25 
{
26
f[x][i]=max(f[x][i],f[tr[x]][i]);
27
for (j=0;j<=con[tl[x]];++j)
28
f[x][i+j+1]=max(f[x][i+j+1],num[x]+f[tr[x]][i]+f[tl[x]][j]);
29 
}
30 }
31 int main()
32 {
33
memset(f,0,sizeof(f));
34
memset(tl,0,sizeof(tl));
35
memset(tr,0,sizeof(tr));
36
memset(con,0,sizeof(con));
37
memset(num,0,sizeof(num));
38
scanf("%d %dn",&N,&M);
39
int i,j,x,y;
40
for (i=1;i<=N;++i)
41 
{
42
scanf("%d %dn",&x,&num[i]);
43 
insect(x,i);
44 
}
45
dfs(tl[0]);
46
printf("%dn",f[tl[0]][M]);
47 }