HDU 1011 Starship Troopers (树dp)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1011

题意：

题目大意是有n个房间组成一棵树，你有m个士兵，从1号房间开始让士兵向相邻的房间出发，每个房间里有一个代价，代价是值/20个士兵，

同时有一个价值，问你花费这m个士兵可以得到的最大价值是多少。

思路：

树上背包，这题比较坑爹。士兵为0，输出0。要是一个房间的cost不足20的倍数也要补全20的倍数。

dp[i][j]表示以i节点为子树的root使用j个士兵的最大价值( 不用管父节点 )，dp[i][j] = max(dp[i][j] , dp[i.son][k] + dp[i][j - k])

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <vector>
 5 using namespace std;
 6 const int N = 105;
 7 int cost[N], val[N];
 8 vector <int> G[N];
 9 int dp[N][N], n, m;
10 
11 void dfs(int u, int p) {
12     int temp = (cost[u] + 19) / 20;
13     if(temp > m)
14         return ;
15     for(int i = temp; i <= m; ++i) {
16         dp[u][i] = val[u];
17     }
18     for(int i = 0; i < G[u].size(); ++i) {
19         int v = G[u][i];
20         if(v == p)
21             continue;
22         dfs(v, u);
23         for(int j = m; j >= temp + 1; --j) { //类似背包 每个可取的值只枚举一次
24             for(int k = temp; k < j; ++k) { //每条路径上会保证有一个士兵
25                 dp[u][j] = max(dp[u][j], dp[u][k] + dp[v][j - k]);
26             }
27         }
28     }
29 }
30 
31 int main()
32 {
33     while(~scanf("%d %d", &n, &m)) {
34         if(m == -1 && n == -1)
35             break;
36         memset(dp, 0, sizeof(dp));
37         for(int i = 1; i <= n; ++i) {
38             G[i].clear();
39             scanf("%d %d", cost + i, val + i);
40         }
41         int u, v;
42         for(int i = 1; i < n; ++i) {
43             scanf("%d %d", &u, &v);
44             G[u].push_back(v);
45             G[v].push_back(u);
46         }
47         dfs(1, -1);
48         if(!m) {
49             printf("0
");
50         } else {
51             printf("%d
", dp[1][m]);
52         }
53     }
54     return 0;
55 }