本文共 1831 字,大约阅读时间需要 6 分钟。
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 #include2 #include 3 #include 4 #include 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 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\n");52 continue;53 }54 memset(dp, 0, sizeof(dp));55 DFS(0, -1);56 printf("%d\n", dp[0][m]);57 }58 return 0;59 }
转载地址:http://jdisa.baihongyu.com/