BZOJ 2101 [Usaco2010 Dec] Treasure Chest 藏寶箱 — 區間博弈 DP 空間優化

題目大意

貝西與邦妮輪流從一排 N (≤ 5000) 枚金幣的兩端各取一枚，雙方均採最優策略，貝西先手。求貝西能獲得的最大總價值。

範例：30 25 10 35 → 貝西先取 35，邦妮取 30，貝西取 25，邦妮取 10，貝西總計 60。

核心觀察

設 f[i][j] 為區間 [i, j] 先手能獲得的最大值。對於區間 [i, j]，先手可取左端或右端：

• 取左端：對手在 [i+1, j] 先手，先手最終得 sum[i+1,j] - f[i+1][j] + a[i]
• 取右端：同理得 sum[i,j-1] - f[i][j-1] + a[j]

化簡後得到遞推：f[i][j] = sum[i,j] - min(f[i+1][j], f[i][j-1])。

空間優化至一維

發現 f[i][j] 僅依賴 f[i+1][j]（下一行同列）與 f[i][j-1]（同行前一列），可壓縮為一維陣列 f[i] 表示當前長度為 len 的區間起點 i 的最優值。按區間長度遞增 DP，每輪更新 f[i] = sum[i+len-1] - sum[i-1] - min(f[i], f[i+1])。

AC 程式碼（C++）

#include 
using namespace std;
const int MAXN = 5005;
int n, a[MAXN];
long long sum[MAXN], f[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        sum[i] = sum[i-1] + a[i];
        f[i] = a[i];                 // 長度 1 區間
    }
    for (int len = 2; len <= n; ++len) {       // 區間長度
        for (int i = 1; i + len - 1 <= n; ++i) {
            f[i] = sum[i+len-1] - sum[i-1] - min(f[i], f[i+1]);
        }
    }
    cout << f[1] << '\n';
    return 0;
}

複雜度分析

• 時間：O(N²)，N ≤ 5000 約 2.5×10⁷ 次操作，極易通過。
• 空間：O(N)，僅需兩個長度 N 的陣列。

關鍵點總結

1. 博弈類 DP 常可轉化為「總和減去對手最優」。
2. 一維滾動陣列關鍵在於識別狀態依賴方向，按正確順序覆蓋即可。
3. 前綴和 sum[] 讓區間和查詢成為 O(1)。