HDU 4597 Play Game 解題報告：區間 DP + 記憶化搜索

遊戲規則

兩排數字，每排長度 n。雙方輪流從任意一排的左右兩端取一個數字，得分為該數字。雙方都採取最優策略，求先手最大得分。

狀態定義

dp[s1][e1][s2][e2] 表示第一排剩餘區間 [s1, e1]、第二排剩餘 [s2, e2] 時，當前玩家能獲得的最大得分差（或絕對得分）。

轉移方程

當前玩家有四種選擇：取第一排左/右，或第二排左/右。對方接著在剩餘區間同樣最優決策。因此：

dp = sum(remaining) - min( 四種選擇後的 dp值 )

其中 sum 為當前所有剩餘數字之和，預處理前綴和 ans[1][i], ans[2][i] 可 O(1) 獲取區間和。

邊界處理

• 某排已空（s > e）：只能從另一排取，轉移簡化為兩種選擇。
• 兩排均空：返回 0。

記憶化搜索實現

int dfs(int s1, int e1, int s2, int e2) {
    if (s1>e1 && s2>e2) return 0;
    if (dp[s1][e1][s2][e2] != -1) return dp[s1][e1][s2][e2];
    int sum = getSum(1,s1,e1) + getSum(2,s2,e2);
    int best = -INF;
    if (s1 <= e1) {
        best = max(best, sum - dfs(s1+1, e1, s2, e2));
        best = max(best, sum - dfs(s1, e1-1, s2, e2));
    }
    if (s2 <= e2) {
        best = max(best, sum - dfs(s1, e1, s2+1, e2));
        best = max(best, sum - dfs(s1, e1, s2, e2-1));
    }
    return dp[s1][e1][s2][e2] = best;
}

複雜度分析

• 狀態數：O(n^4)，n ≤ 20，共 16 萬狀態，每狀態 O(1) 轉移，完全可行。
• 記憶化避免重複計算，配合 #pragma comment(linker, "/STACK:...") 防止遞歸棧溢出。

關鍵點總結

1. 雙序列區間 DP 狀態設計需包含四個端點。
2. 「總和 - 對方最優」的博弈轉移模式是經典套路。
3. 前綴和優化區間求和，記憶化數組初始化為 -1 區分未計算狀態。