題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 🟡 AT_dp_l Deque

Problem Statement

題目簡述

兩人輪流從數列 a=(a1,…,aN)a = (a_1, \ldots, a_N) 的首部或尾部取出一個元素，取出的元素值計入該玩家的得分。
遊戲結束時，先手總得分為 XX，後手總得分為 YY。先手的目標是最大化 X−YX - Y，後手的目標是最小化 X−YX - Y。
求雙方都採取最優策略下的 X−YX - Y 值。

Constraints

約束條件

  • 輸入均為整數。
  • 1≤N≤30001 \leq N \leq 3000
  • 1≤ai≤1091 \leq a_i \leq 10^9

思路：Minimax 區間 DP

定義 f[i][j]f[i][j] 為區間 A[i…j]A[i \dots j] 剩餘時，雙方最優策略下的最終得分差 X−YX - Y。

判斷當前玩家

設 v=i+(N−1−j)v = i + (N - 1 - j) 為已取走的元素數（左邊取了 ii 個，右邊取了 N−1−jN-1-j 個）。

  • vv 為偶數 → 先手回合
  • vv 為奇數 → 後手回合

狀態轉移

每回合可選擇取 A[i]A[i]（左端）或 A[j]A[j]（右端）：

  • 先手回合：希望最大化 X−YX - Y，取到的分數加入 XX

    f[i][j]=max⁡(f[i+1][j]+A[i],  f[i][j−1]+A[j])f[i][j] = \max(f[i+1][j] + A[i],\; f[i][j-1] + A[j])

  • 後手回合：希望最小化 X−YX - Y，取到的分數加入 YY

    f[i][j]=min⁡(f[i+1][j]−A[i],  f[i][j−1]−A[j])f[i][j] = \min(f[i+1][j] - A[i],\; f[i][j-1] - A[j])

邊界條件：i>ji > j 時 f[i][j]=0f[i][j] = 0（區間為空）。答案為 f[0][N−1]f[0][N-1]。

複雜度分析

  • 時間複雜度：O(N2)\mathcal{O}(N^2)
  • 空間複雜度：O(N2)\mathcal{O}(N^2)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def solve():
    n = int(input())
    A = list(map(int, input().split()))

    # @cache
    # def dfs(l: int, r: int) -> int:
    #     if l > r:
    #         return 0
    #     v = l + (n - 1 - r)
    #     if v & 1 == 0:
    #         return max(dfs(l + 1, r) + A[l], dfs(l, r - 1) + A[r])
    #     else:
    #         return min(dfs(l + 1, r) - A[l], dfs(l, r - 1) - A[r])
    # print(dfs(0, n - 1))

    f = [[0] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            v = i + (n - 1 - j)
            f1 = f[i + 1][j] if i < n - 1 else 0
            f2 = f[i][j - 1] if j > 0 else 0
            if v & 1 == 0:
                f[i][j] = max(f1 + A[i], f2 + A[j])
            else:
                f[i][j] = min(f1 - A[i], f2 - A[j])
    print(f[0][n - 1])

if __name__ == "__main__":
    solve()