HDU 1011 Starship Troopers 樹形 DP + 背包

問題模型

樹形洞穴，根節點 1 為入口。每節點有 bugs（需派兵消滅）和 brain_prob（捕獲大腦概率）。每兵消滅 20 隻蟲。共 M 名士兵。士兵進入節點後不再返回。最大化捕獲大腦期望總和。

樹形 DP 狀態定義

dp[u][k]：在以 u 為根的子樹中，投入 k 名士兵，能獲得的最大期望值。

轉移方程（分組背包）

• 節點 u 自身需 need = ceil(bugs[u] / 20) 名兵
• 初始：dp[u][k] = brain[u] (k ≥ need)
• 合併子樹 v：dp[u][j] = max(dp[u][j], dp[u][j-c] + dp[v][c]) (j 從 M 降到 need，c 從 1 到 j-need)

代碼實現

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 105;
int bugs[MAXN], brain[MAXN];
int dp[MAXN][MAXN];
vector<int> G[MAXN];
int N, M;

void dfs(int u) {
    int need = (bugs[u] + 19) / 20;
    for (int k = need; k <= M; ++k) dp[u][k] = brain[u];

    for (int v : G[u]) {
        dfs(v);
        for (int k = M; k >= need; --k)
            for (int c = 1; k-c >= need; ++c)
                dp[u][k] = max(dp[u][k], dp[u][k-c] + dp[v][c]);
    }
}

int main() {
    while (scanf("%d%d", &N, &M) == 2) {
        if (N==-1 && M==-1) break;
        for (int i = 1; i <= N; ++i) {
            scanf("%d%d", &bugs[i], &brain[i]);
            G[i].clear();
        }
        for (int i = 1; i < N; ++i) {
            int u, v; scanf("%d%d", &u, &v);
            G[u].push_back(v); // 題目保證 u 是父節點
        }
        memset(dp, 0, sizeof(dp));
        dfs(1);
        printf("%d\n", dp[1][M]);
    }
    return 0;
}

關鍵細節

• 樹邊輸入保證父子關係（u 為父），無需建無向圖再 DFS 確定父子
• 士兵不可重複使用 → 背包內層倒序枚舉
• 若 k < need，dp[u][k] 保持 0（不可行）
• 複雜度：O(N × M²)，N,M≤100 時 10⁶ 級，可接受