HDU 4597 Play Game：雙端取牌博弈 DP + 記憶化搜索

題目大意

兩堆各 n 張牌，每張有分值。Alice 先手，雙方輪流從任一堆的**兩端**取一張牌（共 4 個選擇）。求 Alice 能獲得的最大分數和。

博弈 DP 模型

設 dfs(a,b,c,d) 表示當前剩餘第一堆 [a,b]，第二堆 [c,d] 時，**當前玩家**能獲得的最大分數。總分固定，雙方最優博弈下：

當前玩家得分 = 剩餘總分 - 對手最優得分

即：dfs(a,b,c,d) = sum(a,b,c,d) - max( 選項得分 + dfs(選項後狀態) )

狀態轉移

• 從第一堆取左：x[a] + dfs(a+1,b,c,d)
• 從第一堆取右：x[b] + dfs(a,b-1,c,d)
• 從第二堆取左：y[c] + dfs(a,b,c+1,d)
• 從第二堆取右：y[d] + dfs(a,b,c,d-1)
• 取四者最大值作為對手最優得分，用總分減去得到當前玩家得分。

代碼實現

#include <bits/stdc++.h>
using namespace std;

const int M = 55;
int n, dp[M][M][M][M];
int x[M], y[M], sum1[M], sum2[M];

int dfs(int a, int b, int c, int d) {
    if (a > b && c > d) return 0;
    int &res = dp[a][b][c][d];
    if (res) return res;

    int sum = sum1[b] - sum1[a-1] + sum2[d] - sum2[c-1];
    int best = 0;
    if (a <= b) best = max(best, max(x[a] + dfs(a+1,b,c,d), x[b] + dfs(a,b-1,c,d)));
    if (c <= d) best = max(best, max(y[c] + dfs(a,b,c+1,d), y[d] + dfs(a,b,c,d-1)));
    return res = sum - best;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        memset(dp, 0, sizeof(dp));
        sum1[0] = sum2[0] = 0;
        for (int i = 1; i <= n; i++) { scanf("%d", &x[i]); sum1[i] = sum1[i-1] + x[i]; }
        for (int i = 1; i <= n; i++) { scanf("%d", &y[i]); sum2[i] = sum2[i-1] + y[i]; }
        printf("%d\n", sum1[n] + sum2[n] - dfs(1, n, 1, n));
    }
    return 0;
}

關鍵技巧

• 前綴和：sum1[i], sum2[i] 快速計算區間總分。
• 記憶化搜索：四維 DP 狀態 (a,b,c,d)，n≤50 ⇒ 50⁴=6.25e6 狀態，但實際可達狀態遠少，配合遞歸 + 記憶化極快。
• 博弈轉化：直接求當前玩家得分，避免雙人 DP 狀態翻倍。

複雜度分析

• 狀態數：O(n⁴) 理論上限，實際約 O(n³) 量級（兩堆獨立）。
• 每狀態 O(1) 轉移。總時間 < 0.1s。
• 空間：O(n⁴) ≈ 6.25e6 int ≈ 25MB，可接受。

總結

雙堆雙端取牌博弈，用「總分 - 對手最優」轉化為單人 DP，記憶化搜索實現簡潔高效。前綴和優化區間求和，四維數組直接索引狀態，是區間博弈 DP 的標準模板。