HDU 1561：樹形 DP——城堡寶物最大化選取問題

題目大意

有 N 座城堡，每座城堡有寶物值。城堡間存在依賴關係：攻克城堡 i 必須先攻克城堡 a（a=0 表示無依賴，可直接攻克）。需恰好選 M 個城堡攻克，使獲得的寶物總值最大。N, M ≤ 200，多組測試數據以 0 0 結束。

樹形 DP 建模

依賴關係形成一棵以 0 為虛擬根的森林（實際上是一棵樹，因所有節點最終指向 0）。每個節點代表一個城堡，邊表示依賴（父節點必須先於子節點被選）。問題轉化為：在樹上選恰好 M 個節點，若選某節點必須選其所有祖先，最大化權值和。

狀態定義

dp[u][k]：以 u 為根的子樹中，選擇 k 個節點（包含 u）所能獲得的最大寶物值。
val[u]：城堡 u 的寶物值。
sz[u]：子樹 u 中可選節點數（即子樹大小）。

狀態轉移

初始化：dp[u][0] = 0，dp[u][1] = val[u]（若 u 非虛擬根），其餘設為 -INF。
對每個子節點 v，進行背包式合併：

for (int k = sz[u]; k >= 1; k--)
    for (int t = 1; t <= sz[v] && t <= k; t++)
        dp[u][k] = max(dp[u][k], dp[u][k-t] + dp[v][t]);

合併後更新 sz[u] += sz[v]。虛擬根 0 的 val[0] = 0，最終答案為 dp[0][M]。

代碼實現

#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;

vector<int> map[305];
int dp[305][305], val[305], sz[305], vis[305], N, M;

int max(int a, int b) { return a > b ? a : b; }

void dfs(int u) {
    vis[u] = 1;
    sz[u] = 1;
    for (int i = 0; i <= N; i++) dp[u][i] = -1e9;
    dp[u][0] = 0;
    if (u) dp[u][1] = val[u]; // 虛擬根 0 不計寶物

    for (int v : map[u]) {
        if (vis[v]) continue;
        dfs(v);
        for (int k = sz[u]; k >= 1; k--)
            for (int t = 1; t <= sz[v] && t <= k; t++)
                dp[u][k] = max(dp[u][k], dp[u][k-t] + dp[v][t]);
        sz[u] += sz[v];
    }
}

int main() {
    while (scanf("%d%d", &N, &M) > 0) {
        if (N == 0 && M == 0) break;
        for (int i = 0; i <= N; i++) map[i].clear(), vis[i] = 0;
        for (int i = 1; i <= N; i++) {
            int a, b;
            scanf("%d%d", &a, &b);
            map[a].push_back(i); // a 是 i 的父節點
            val[i] = b;
        }
        dfs(0);
        printf("%d\n", dp[0][M]);
    }
    return 0;
}

關鍵點總結

• 虛擬根 0 統一處理多棵子樹，方便 DP 合併。
• 初始化 dp[u][*] = -INF 避免非法狀態轉移。
• 背包合併時外層循環逆序，防止重複使用同一子樹節點。
• 複雜度 O(N·M²)，N,M ≤ 200 完全可行。