HDOJ 1561 The more, The Better（树形DP）

思路：

有依赖的背包、泛化背包的思想，和“金明的预算方案”那题是一样的。

dp[u][i] 表示 u 为根节点的子树，要攻击 i 个城堡所获得的最大金钱数目。其中 u 城堡是已经攻下来的。

则 dp[u][i] = max(dp[u][i], dp[v][i-1] + val[v]);

题目中设置出发点位 0，这样的话就可以把森林变成一个棵树，方便于解题。

解一：采用了泛化物品的并的 O(n * V) 优化解法，15ms

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 210;

struct edge {
    int v, c;
    edge* next;
} *V[MAXN], ES[MAXN * 2];

int EC, dp[MAXN][MAXN], val[MAXN];
bool vis[MAXN];

void addedge(int u, int v)
{
    ES[++EC].next = V[u];
    V[u] = ES + EC; V[u]->v = v;
}

void initdata(int n)
{
    EC = 0;
    memset(V, 0, sizeof(V));
    memset(vis, false, sizeof(vis));

    for (int u = 1; u <= n; ++u)
    {
        int v;
        scanf("%d %d", &v, &val[u]);
        addedge(v, u);
    }
}

void treedp(int u, int vol)
{
    vis[u] = true;

    for (edge* e = V[u]; e; e = e->next)
    {
        if (vis[e->v])
            continue;

        for (int i = vol; i >= 0; --i)
            dp[e->v][i] = dp[u][i];

        treedp(e->v, vol - 1);

        for (int i = vol; i >= 1; --i)
            dp[u][i] = max(dp[u][i], dp[e->v][i-1] + val[e->v]);
    }
}

int main()
{
    int n, m;
    while (scanf("%d %d", &n, &m) && n && m)
    {
        initdata(n);
        memset(dp[0], 0, sizeof(dp[0]));
        treedp(0, m);
        printf("%d\n", dp[0][m]);
    }
    return 0;
}

解法二：普通解法 O(n * V * V)

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 210;

struct edge {
    int v, c;
    edge* next;
} *V[MAXN], ES[MAXN * 2];

int EC, dp[MAXN][MAXN], val[MAXN];
bool vis[MAXN];

void addedge(int u, int v)
{
    ES[++EC].next = V[u];
    V[u] = ES + EC; V[u]->v = v;
}

void initdata(int n)
{
    EC = 0;
    memset(V, 0, sizeof(V));
    memset(vis, false, sizeof(vis));

    for (int u = 1; u <= n; ++u)
    {
        int v;
        scanf("%d %d", &v, &val[u]);
        addedge(v, u);
    }
    memset(dp, 0, sizeof(dp));
}

void treedp(int u, int vol)
{
    vis[u] = true;

    for (edge* e = V[u]; e; e = e->next)
    {
        if (vis[e->v])
            continue;

        treedp(e->v, vol - 1);

        for (int i = vol; i >= 1; --i)
            for (int j = 1; j <= i; ++j)
                dp[u][i] = max(dp[u][i], dp[u][j-1] + dp[e->v][i-j] + val[e->v]);
    }
}

int main()
{
    int n, m;
    while (scanf("%d %d", &n, &m) && n && m)
    {
        initdata(n);
        treedp(0, m);
        printf("%d\n", dp[0][m]);
    }
    return 0;
}