Starship Troopers

HDU的一道常规动态规划题目。

题目重述：

每个队员都能够对付20只虫子，但是如果有21只虫子，你也得出2个人来对付。输入数据中，先是N(N <= 100)个洞穴，然后再是M(M <= 100)个队员。然后输入N个洞穴的信息，包括有多少只虫子，其中存在Boss的概率是多少。然后再是洞穴的联通情况，双向连通。在处理保存虫子的数组时实际上是耗费队员的数组 bug[i] = (bug[i] + 19)/20; 。

转移方程：

通过DFS进行遍历，转移方程为 dp[当前洞穴][耗费人数] = max{dp[当前洞穴][耗费人数],dp[当前洞穴][当前洞穴派走了k个人] + dp[子洞穴][派往子洞穴k个人]}，这是一道树形DP题。

源代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<vector>
 5 #define MAXN 105
 6 using namespace std;
 7 int dp[MAXN][MAXN];
 8 int m,n;
 9 int bug[MAXN];
10 int possible[MAXN];
11 vector<int>cavern[MAXN];
12 
13 void DFS(int root, int pos)
14 {
15     for(int i = bug[root]; i <= m; i++)
16         dp[root][i] = possible[root];
17     int tot = (int)cavern[root].size();
18     for(int i = 0; i < tot; i++)
19     {
20         int v = cavern[root][i];
21         if(v == pos)
22             continue;
23         DFS(v, root);
24         for(int j = m; j >= bug[root]; j--)
25             for(int k = 1; k <= j-bug[root]; k++)
26             {
27                 dp[root][j] = max(dp[root][j], dp[root][j-k] + dp[v][k]);
28             }
29     }
30 }
31 
32 int main()
33 {
34     while(~scanf("%d%d", &n, &m) && n != -1 || m != -1)
35     {
36         for(int i = 0; i < n; i++)
37         {
38             scanf("%d%d", &bug[i], &possible[i]);
39             bug[i] = (bug[i] + 19)/20;
40         }
41         for(int i = 0; i < n; i++)
42             cavern[i].clear();
43         for(int i = 0, a, b; i < n-1; i++)
44         {
45             scanf("%d%d", &a, &b);
46             cavern[a-1].push_back(b-1);
47             cavern[b-1].push_back(a-1);
48         }
49         if(m == 0)
50         {
51             printf("0
");
52             continue;
53         }
54         memset(dp, 0, sizeof(dp));
55         DFS(0, -1);
56         printf("%d
", dp[0][m]);
57     }
58     return  0;
59 }