HDU 1561 The more, The Better：樹形 DP + 背包選城堡最大化寶物

題目簡介

N 座城堡（N ≤ 200），每座有寶物值。攻克城堡需先攻克其前置城堡（形成樹/森林）。最多攻克 M 座，求最大寶物總值。

解題思路

樹形 DP + 分組背包：

• 以無前置城堡（a=0）為根，建立樹/森林。
• dp[u][k] 表示在以 u 為根的子樹中選 k 個城堡（必選 u）的最大寶物值。
• 初始化 dp[u][1] = value[u]。
• 合併子樹 v 到 u：for i = M..1; for j = 1..i-1; dp[u][i] = max(dp[u][i], dp[u][i-j] + dp[v][j])。
• 虛擬根 0 連接所有根，最終答案 dp[0][M]（或枚舉所有根取最大）。

代碼框架

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 205;
int val[N], n, M;
vector<int> g[N];
int dp[N][N];
bool vis[N];

void dfs(int u) {
    vis[u] = true;
    dp[u][1] = val[u];
    for (int v : g[u]) if (!vis[v]) {
        dfs(v);
        for (int i = M; i >= 1; i--)
            for (int j = 1; j < i; j++)
                dp[u][i] = max(dp[u][i], dp[u][i-j] + dp[v][j]);
    }
}

int main() {
    while (cin >> n >> M, n||M) {
        for (int i=1;i<=N;i++) g[i].clear();
        memset(dp, 0, sizeof(dp));
        memset(vis, 0, sizeof(vis));
        for (int i=1;i<=n;i++) {
            int a, b; cin >> a >> b;
            val[i] = b;
            if (a == 0) g[0].push_back(i);
            else g[a].push_back(i);
        }
        dfs(0);
        cout << dp[0][M] << endl;
    }
    return 0;
}

複雜度分析

每條邊合併一次背包，總複雜度 O(N × M^2) 或優化後 O(N × M)，N,M ≤ 200 完全可行。