[HDU][ACM]1561 The more, The Better
海胖子 - 2014/03/20题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1561 题目大意:在一个有N座城堡的地图上,攻克城堡能获得宝物,游戏中需要攻克某城堡才能攻克其它城堡。如果一共只能攻克M座城堡,求能获得最大的宝物数量。 算法:树形动态规划 注意事项:用链表建树,构造函数初始化,析构函数删除节点。
/* * Author: Haipz * School: HDU * File Name: 1561.cpp */ #include <cstdio> #include <cmath> #include <ctime> #include <cctype> #include <cfloat> #include <cstdlib> #include <cstring> #include <climits> #include <iostream> #include <vector> #include <stack> #include <queue> #include <set> #include <map> #include <algorithm> using namespace std; const int N = 2e2, M = 2e2; struct node { int dp[N + 5]; int value; node *bro, *son; node() { memset(dp, 0, sizeof(dp)); value = 0; bro = son = NULL; } ~node() { if (bro != NULL) delete bro; if (son != NULL) delete son; } }; int a[N + 5][N + 5]; void build(node *root, int x, int n) { for (int i = 1; i <= n; ++i) if (a[x][i] != -1) { node *tmp = new node(); tmp->bro = root->son; tmp->value = a[x][i]; root->son = tmp; build(root->son, i, n); } return; } void dp(node *root, int m) { root->dp[1] = root->value; if (root->son == NULL) return; node *tmp = root->son; while (tmp != NULL) { if (m > 1) dp(tmp, m - 1); for (int i = m + 1; i >= 2; --i) for (int j = i - 1; j >= 1; --j) root->dp[i] = max(root->dp[i], root->dp[i - j] + tmp->dp[j]); tmp = tmp->bro; } return; } int main() { int n, m; while (scanf("%d%d", &n, &m) && n && m) { memset(a, -1, sizeof(a)); for (int i = 1; i <= n; ++i) { int p, v; scanf("%d%d", &p, &v); a[p][i] = v; } node *root = new node(); build(root, 0, n); dp(root, m); printf("%d\n", root->dp[m + 1]); } return 0; }
转载保留版权:http://haipz.com/blog/i/847 - 海胖博客