vijos p1180 选课_小小_新浪博客

vijos p1180 选课_小小_新浪博客

个整数N、M（中间用一个空格隔开）其中1≤N≤300,1≤M≤N。 以下N行每行代表一门课。课号依次为1，2，…，N。每行有两个数（用一个空格隔开），第一个数为这门课先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。学分是不超过10的正整数。

	输出格式 Output Format
		输出文件只有一个数,实际所选课程的学分总数。

顾名思义，树型动态规划就是在“树”的数据结构上的动态规划，平时作的动态规划都是线性的或者是建立在图上的，线性的动态规划有二种方向既向前和向后，相应的线性的动态规划有二种方法既顺推与逆推，而树型动态规划是建立在树上的，所以也相应的有二个方向：
1. 根—>叶：不过这种动态规划在实际的问题中运用的不多，也没有比较明显的例题。
2. 叶－>根：既根的子节点传递有用的信息给根，完后根得出最优解的过程。

而树形DP的实现也是比较特别的，一般采用记忆化搜索，而不是传统的迭代形式。

首先把一棵普通树转化为二叉树：第一个孩子作为父节点的左子树，其它孩子作为第一个孩子的右子树。
f(x，y)：表示节点x取y门课得最高学分，则
f(x，y)＝max{ max{ f(x.left,k)+x.v+f(x.right,y-k-1), k=0,1,..y }, f(x.right,y) }
f(x.l,k）+x.v(课程x的学分):表示选了课程x,左孩子选k门课,共k+1门课。
f(x.r,y-k-1)表示右孩子只能选y-k-1门课。

06 struct node{
07     int l,r,s,d;
08 } tree[MAXN+1];
09 int f[MAXN+1][MAXN+2],n,m,p1[MAXN+1],p2[MAXN+1];
10 
11 void build(int x){
12     int i,k=x;
13     tree[x].d=p2[x];
14     for(i=1;i<=n;++i)
15         if(p1[i]==x){
16             if(k==x)
17                 tree[x].l=i;
18             else
19                 tree[k].r=i;
20             build(i);
21             k=i;
22         }
23 }
24 
25 void travel(int x){
26     if(tree[x].l){
27         travel(tree[x].l);
28         tree[x].s+=tree[tree[x].l].s;
29     }
30     if(tree[x].r){
31          travel(tree[x].r);
32         tree[x].s+=tree[tree[x].r].s;
33     }
34     tree[x].s++;
35 }
36 
37 int solve(int x,int k){
38     int i,ma=0,left=tree[x].l,right=tree[x].r;
39     if(k<=0)
40         return 0;
41     if(f[x][k]!=0)
42         return f[x][k];
43     if(tree[x].s==1)
44         return f[x][k]=tree[x].d;
45 
46     if(right && tree[right].s>=k)                //left.num=0，这时left不是必须存在
47         ma=max(ma,solve(right,k));
48     if(right && tree[right].s>=k-1)
49         ma=max(ma,solve(right,k-1)+tree[x].d);
50     if(left){
51         for(i=1;i<=k-2;++i)                       //left.num=i
52             if(tree[left].s>=i){
53                 if(right && tree[right].s>=k-1-i)
54                    ma=max(ma,solve(left,i)+tree[x].d+solve(right,k-1-i));
55             }else break;
56         ma=max(ma,solve(left,k-1)+tree[x].d);          //把 k-1-i=0 拿出来是因为这时right不是必须存在
57     }
58     return f[x][k]=ma;
59 }
60 
61 int main(){
62 #ifdef _HOME_
63     freopen("input.txt","r",stdin);
64     freopen("output.txt","w",stdout);
65 #endif
66     int i;
67     cin>>n>>m;
68     for(i=1;i<=n;++i)
69         cin>>p1[i]>>p2[i];
70     build(0);
71     travel(tree[0].l);
72     cout<<solve(tree[0].l,m)<<endl;
73     return 0;
74 }
Read full article from vijos p1180 选课_小小_新浪博客