HDU 5115 Dire Wolf：區間 DP 消滅狼群最小代價

題目大意

一排 n (≤ 200) 隻狼，第 i 隻有攻擊力 a[i]、防禦力 b[i]。每次選一隻狼消滅，代價 = 其攻擊力 + 左右相鄰存活狼的防禦力（邊界視為 0）。求消滅所有狼的最小總代價。多測試案例。

區間 DP 狀態定義

dp[l][r] = 當前存活狼區間為 [l, r] 時，消滅該區間所有狼的最小代價。
邊界：b[0] = b[n+1] = 0。
目標：dp[1][n]。

轉移方程（正向構建：由小區間擴展到大區間）

考慮區間 [l, r] 最後消滅的是哪隻狼 k (l ≤ k ≤ r)：
- 消滅 k 時代價 = a[k] + b[l-1] + b[r+1]（當時左右鄰居為 l-1 和 r+1）。
- 剩餘 [l, k-1] 和 [k+1, r] 獨立消滅。
dp[l][r] = min_{k=l..r} ( dp[l][k-1] + dp[k+1][r] + a[k] + b[l-1] + b[r+1] )

初始化與邊界

• dp[i][i] = a[i] + b[i-1] + b[i+1]
• dp[i][i+1] = min( dp[i][i] + a[i+1] + b[i-1] + b[i+2], dp[i+1][i+1] + a[i] + b[i-1] + b[i+2] )
• dp[l][r] = INF 初始。

關鍵代碼

const int INF = 1e9;
int a[205], b[205], dp[205][205];

void init(int n) {
    for (int i = 0; i <= n+1; ++i)
        for (int j = 0; j <= n+1; ++j)
            dp[i][j] = INF;
    b[0] = b[n+1] = 0;
    for (int i = 1; i <= n; ++i) dp[i][i] = a[i] + b[i-1] + b[i+1];
    for (int i = 1; i < n; ++i)
        dp[i][i+1] = min(dp[i][i] + a[i+1] + b[i-1] + b[i+2],
                         dp[i+1][i+1] + a[i] + b[i-1] + b[i+2]);
}

int main() {
    int T; scanf("%d", &T);
    for (int cas = 1; cas <= T; ++cas) {
        int n; scanf("%d", &n);
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        for (int i = 1; i <= n; ++i) scanf("%d", &b[i]);
        init(n);
        for (int len = 3; len <= n; ++len) {
            for (int l = 1; l + len - 1 <= n; ++l) {
                int r = l + len - 1;
                // 先考慮邊界消滅
                dp[l][r] = min(dp[l][r], dp[l+1][r] + a[l] + b[l-1] + b[r+1]);
                dp[l][r] = min(dp[l][r], dp[l][r-1] + a[r] + b[r+1] + b[l-1]);
                // 再考慮中間點
                for (int k = l+1; k <= r-1; ++k)
                    dp[l][r] = min(dp[l][r], dp[l][k-1] + dp[k+1][r] + b[l-1] + b[r+1] + a[k]);
            }
        }
        printf("Case #%d: %d\n", cas, dp[1][n]);
    }
    return 0;
}

複雜度

• 狀態數 O(n²)，轉移 O(n)，總 O(n³) = 8×10⁶，n=200 完全可行。
• 空間 O(n²) = 4×10⁴。

關鍵洞見

• **正向 DP**：dp[l][r] 表示「當前區間為 [l,r] 時消滅它們的代價」，而非「最後剩 [l,r] 的代價」。這樣轉移時左右邊界固定為 l-1, r+1，公式統一。
• **邊界預處理**：b[0]=b[n+1]=0 統一邊界條件。
• **長度遞增枚舉**：保證子區間已計算。

總結

HDU 5115 是經典的「區間 DP 最後一步拆分」問題。關鍵在於正確定義狀態語義（正向 vs 逆向），並處理好邊界防禦力。代碼結構清晰，是區間 DP 入門佳作。