首页 > 代码库 > HDU 1011 Starship Troopers 树DP
HDU 1011 Starship Troopers 树DP
本题也是挺特别的题目,由于要递归到树的叶子节点然后初始化。
一開始看题也非常困难,以为仅仅是一条路径的最大获利计算。使用保存路径,然后DP。结果WA了。
原来本题是须要分路径探索的。就是说每个分岔路都能够分兵探索下去,假设兵力不足就结束,看最大收益是多少。
题目并没有说的那么清楚,或许看题目也考人的IQ吧。要放聪明点。
本题是考人的递归能力。动态规划法能力,总结起来难度还是非常高的。
#include <stdio.h> #include <vector> #include <algorithm> #include <math.h> using namespace std; int N, M, a, b; vector<vector<int> > *ca; vector<bool> *vis; vector<vector<int> > *tbl; vector<vector<int> > *tu; //不使用全局变量,就要传递6个变量给treeDP void treeDP(int r) { (*vis)[r] = true; int soldiers = ((*ca)[r][0]+19)/20; //单独是本节点的时候,多少soldiers以上能拿到brain,递归究竟就作为初始化条件了 for (int i = soldiers; i <= M; i++) (*tbl)[r][i] = (*ca)[r][1]; for (int i = 0; i < (int)(*tu)[r].size(); i++) { int u = (*tu)[r][i]; if ((*vis)[u]) continue; treeDP(u);//深度递归究竟出来。就已经初始化好最小情况了 for (int j = M-1; j >= soldiers; j--) {//j为本节点兵力 for (int k = 1; k <= M-j; k++) {//k为分配多少给孩子节点的兵力 (*tbl)[r][j+k]=max((*tbl)[r][j+k],(*tbl)[r][j]+(*tbl)[u][k]); }//试探性分配兵力,从1分配到M-soldiers给孩子节点 } } } int main() { while (scanf("%d %d", &N, &M) && -1 != N) { vector<vector<int> > caverns(N+1, vector<int>(2)); for (int i = 1; i <= N; i++) { scanf("%d %d", &caverns[i][0], &caverns[i][1]); } ca = &caverns;//降低传递參数 vector<vector<int> > tunnels(N+1); for (int i = 1; i < N; i++) { scanf("%d %d", &a, &b); tunnels[a].push_back(b); tunnels[b].push_back(a); } tu = &tunnels; if(M == 0) puts("0"); else { vector<bool> visited(N+1, false); vis = &visited; vector<vector<int> > table(N+1, vector<int>(M+1)); tbl = &table; treeDP(1); printf("%d\n", table[1][M]); } } return 0; }
HDU 1011 Starship Troopers 树DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。