博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Starship Troopers
阅读量:6256 次
发布时间:2019-06-22

本文共 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 #include
2 #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/

你可能感兴趣的文章
创建和编辑 crontab 文件
查看>>
钉钉发消息
查看>>
centos7 防火墙端口增加白名单
查看>>
Lucky Sum
查看>>
城市承灾体脆弱性和易损性的影响因素
查看>>
2019.1.22 区块链论文翻译
查看>>
centos7上修改主机名
查看>>
样式技巧总结
查看>>
python 获取当前ip
查看>>
plsql developer中,清除登录历史
查看>>
mysql中,创建包含json数据类型的表?创建json表时候的注意事项?查询json字段中某个key的值?...
查看>>
Json、JavaBean、String等互转
查看>>
Python-列表
查看>>
多线程
查看>>
[CF949C]Data Center Maintenance
查看>>
增强for循环的使用详解及代码
查看>>
程序员优化程序流程
查看>>
6 ZigZag Conversion
查看>>
[react-router] 平时积累
查看>>
强类型数据集
查看>>