海胖博客

题目链接：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 - 海胖博客