hdu1011

/*比较苦逼的树形DP,慢慢来吧!不着急*/ #include <iostream> #include <vector> using namespace std; const int SIZE = 105;

int roomNumber, trooperNumber; int cost[SIZE], brain[SIZE]; int dp[SIZE][SIZE]; /*dp[u][p]表示用 P 个士兵占领以 u 为根节点的子树所能获得的概率最大值*/ vector<int> adj[SIZE]; /*图*/

void dfsPulsDp(int p, int pre) { for (int i = cost[p]; i <= trooperNumber; ++i) /*初始化,首先将dp[p][i]里面填充进brain[p],后面可以更新dp[p][i]的值*/ dp[p][i] = brain[p]; /*也就是说当我们有cost[p]名队员以至于更多时,我们最少可以获得brain[p]个大脑*/ int num = adj[p].size(); /*num指p节点含有的支路数*/ for (int i = 0; i < num; ++i) /*一条支路一条支路遍历,也就是所谓的dfs*/ { int v = adj[p][i]; if (v == pre) continue; /*避免死循环,节点如果是根部,就继续*/ dfsPulsDp (v, p); /*递归解决问题,先将子节点的所能得到的最大值计算出来*/

for (int j = trooperNumber; j >= cost[p]; --j) /*当队员人数一定时*/ for (int k = 1; k <= j - cost[p]; ++k) /*由于p节点一定要通过,所以一定要花费cost[p]*/ if (dp[p][j] < dp[p][j - k] + dp[v][k]) {/*v节点就两种状态,要么选择,要么不选择,选择的话dp[p][j] = dp[p][j - k] + dp[v][k],不选择的话就不变*/ dp[p][j] = dp[p][j - k] + dp[v][k]; } } }

int main() { while ((cin >> roomNumber >> trooperNumber) && (roomNumber != -1) && (trooperNumber != -1)) { int bug, bi1, bi2; int i; for (i = 0; i < roomNumber; i++) { cin >> bug >> brain[i]; cost[i] = (bug + 19) / 20; } for (i = 0; i < roomNumber; i++) adj[i].clear();

for (i = 0; i < roomNumber - 1; i++) { cin >> bi1 >> bi2; adj[bi1 - 1].push_back(bi2 - 1); adj[bi2 - 1].push_back(bi1 - 1); }

if (trooperNumber == 0) { cout << '0' << endl; continue; }

memset(dp, 0, sizeof(dp)); dfsPulsDp(0, -1); cout << dp[0][trooperNumber] << endl; } return 0; }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据小魔方

R语言可视化——多系列柱形图(条形图)与分面组图美化技巧!

今天跟大家分享多系列与分面组图的美化技巧! 昨天讲的关于多序列柱形图与条形图美化技巧,其实还漏掉了一些一点儿。 当数据序列比较多的时候,特别是超过四个以后,还用...

64770
来自专栏AI研习社

Github 项目推荐 | 中文突发事件语料库

https://github.com/shijiebei2009/CEC-Corpus

25840
来自专栏思影科技

《大话脑成像》系列之五——fMRI中的FDR校正

佩大神说他一百万美元不要了,都要关注思影科技! 当我们招完被试(求爷爷拜奶奶,四处张贴小广告),收完数据(每天晚上拖着疲倦的身体扫被试到凌晨),做完预处理,统计...

44660
来自专栏思影科技

失匹配负波可以预测临床精神病高风险人群的预后改善

研究表明,失匹配负波(MMN)幅度或可作为生物标记,用于预测临床精神病高风险人群的预后状况。其中,高风险--症状未缓解的被试MMN幅度显著偏低。该文由韩国首尔国...

37250
来自专栏生信技能树

哪怕是到了2018年,RNA-seq仍然可以不做重复

但是2018年二月的一篇文章,仍然是不做重复,文章是: Transcriptional Regulation of the Warburg Effect in ...

23020
来自专栏生信宝典

GSEA富集分析 - 界面操作

GSEA定义 Gene Set Enrichment Analysis (基因集富集分析)用来评估一个预先定义的基因集的基因在与表型相关度排序的基因表中的分布趋...

42580
来自专栏SDNLAB

5G革命的技术,一个都不能少

第五代移动网络简称5G是产业界即将实现的移动技术革命,是LTE-A网络的深层演进技术。5G网络中的关键技术包括MIMO、OFDM、SC-FDMA等。 超密集微型...

486120
来自专栏机器学习人工学weekly

机器学习人工学weekly-2018/5/27

Prefrontal cortex as a meta-reinforcement learning system

15340
来自专栏about云

使用Spark MLlib给豆瓣用户推荐电影

问题导读: 1.常用的推荐算法有哪些? 2.推荐系统是什么样的流程? 3.从这个推荐系统我们能学到什么? 推荐算法就是利用用户的一些行为,通过一些数学算法,推测...

85670
来自专栏专知

【论文推荐】最新六篇聊天机器人相关论文—弱监督信息、内容驱动、对话管理系统、可扩展情感序列到序列、自主性

24720

扫码关注云+社区

领取腾讯云代金券