Vijos 1180 选课（树形DP）

题目链接

参考题解做的，如果不是在树上，应该就是个普通的二维DP，前i门课选j门取得最大的分数，可是这个题每门课可能有先修课，所以建树，在树上进行递归。在和虎哥讨论了一下，如何建树，由于不是二叉树，所以每门课可能有多个孩子，本来想用邻接表的，但是好像很麻烦，递归起来不知怎么办，还有另一种方式就是左儿子右兄弟的方式，以前没用过，搜了下题解，这样建树状态转移就简单了，就和在URAL做的那个二叉树的树形DP差不多了。开始的时候也有另一种想法，先把各个点都给重新离散编上号，然后就可以转换为递推的形式了，不知是否可行。

这个还是用静态的做法做的。。。第一这样建树，学习了。。。

1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 #include <math.h>
 5 struct node
 6 {
 7     int left,right;
 8 };
 9 int max(int a,int b)
10 {
11     return a > b ? a:b;
12 }
13 struct node tree[301];
14 int map[301][301],p[301];
15 void insert(int son,int father)
16 {
17     int t;
18     if(!tree[father].left)
19     {
20         tree[father].left = son;
21     }
22     else
23     {
24         t = tree[father].left;
25         while(tree[t].right)
26         {
27             t = tree[t].right;
28         }
29         tree[t].right = son;
30     }
31 }
32 int dp(int x,int y)
33 {
34     int i;
35     if(map[x][y] > 0)
36     return map[x][y];
37     if(x == 0||y == 0)
38     {
39         map[x][y] = 0;
40         return map[x][y];
41     }
42     map[x][y] = dp(tree[x].right,y);
43     for(i = 0;i <= y-1;i ++)//注意从0开始，第一次由于这个没过样例，乱搞了一下。。
44     {
45         map[x][y] = max(map[x][y],dp(tree[x].left,i)+dp(tree[x].right,y-i-1)+p[x]);
46     }
47     return map[x][y];
48 }
49 int main()
50 {
51     int n,m,i,fa;
52     scanf("%d%d",&n,&m);
53     for(i = 1;i <= n;i ++)
54     {
55         scanf("%d%d",&fa,&p[i]);
56         insert(i,fa);
57     }
58     printf("%d\n",dp(tree[0].left,m));
59     return 0;
60 }      

转载于:https://www.cnblogs.com/naix-x/archive/2012/09/04/2670407.html