hdu 1561（树形dp）

说好的开始搞树形DP，前两天一直沉迷于游戏之中，昨天又玩了一整天炉石。ORZ

今天搞搞憋出了第一道。中文题就不说题意了

思路：dp[i][j]表示以i为根的子树攻克j个城堡的最大收获。一开始的时候要加一个零号结点上去，指向所有能被直接攻克的点。然后初始dp[v][1] = vex[v]（状态转移从1开始）原因是先要攻克根才能攻克子树所以要更新子树的话根是一定要被攻克的。然后dp[v][k+j] = max(dp[v][k+j], dp[v][k]+dp[ch][j]) ch枚举每颗子树。

代码如下：

 1 /**************************************************
 2  * Author     : xiaohao Z
 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/
 4  * Last modified : 2014-04-02 11:38
 5  * Filename     : hdu_1561.cpp
 6  * Description     : 
 7  * ************************************************/
 8 
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <cstdlib>
13 #include <cmath>
14 #include <algorithm>
15 #include <queue>
16 #include <stack>
17 #include <vector>
18 #include <set>
19 #include <map>
20 #define MP(a, b) make_pair(a, b)
21 #define PB(a) push_back(a)
22 
23 using namespace std;
24 typedef long long ll;
25 typedef pair<int, int> pii;
26 typedef pair<unsigned int,unsigned int> puu;
27 typedef pair<int, double> pid;
28 typedef pair<ll, int> pli;
29 typedef pair<int, ll> pil;
30 
31 const int INF = 0x3f3f3f3f;
32 const double eps = 1E-6;
33 const int LEN = 1010;
34 vector<int> Map[LEN];
35 int n, m, vex[LEN], dp[LEN][LEN], num[LEN];
36 
37 int dfs(int v, int f){
38     num[v] = 1;
39     dp[v][1] = vex[v];
40     for(int i=0; i<Map[v].size(); i++) 
41         if(Map[v][i] != f){
42             num[v] += dfs(Map[v][i], v);
43         }
44             
45     for(int i=0; i<Map[v].size(); i++){
46         if(Map[v][i] != f){
47             int ch = Map[v][i];
48             for(int k=num[v]; k>0; k--)
49                 for(int j=0; j<=num[ch]; j++){
50                     dp[v][k+j] = max(dp[v][k+j], dp[v][k]+dp[ch][j]);
51                 }
52         }
53     }
54     return num[v];
55 }
56 
57 int main()
58 {
59 //    freopen("in.txt", "r", stdin);
60 
61     int a;
62     while(cin >> n >> m){
63         if(!n && !m) break;
64         for(int i=0; i<LEN; i++)Map[i].clear();
65         memset(dp, 0, sizeof dp);
66         vex[0] = 0;
67         for(int i=1; i<=n; i++){
68             cin >> a >> vex[i];
69             Map[a].PB(i);
70         }
71         dfs(0, -1);
72         cout << dp[0][m+1] << endl;
73     }
74     return 0;
75 }

View Code