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