Overview

Takahashi and Aoki take turns picking cards from either end of a row of cards, and the goal is to maximize the value of Takahashi’s score minus Aoki’s score.

Analysis

In this game, each player needs to act not to “maximize their own score” but to “maximize the score difference between themselves and their opponent.” In other words, simply greedily choosing the larger number is not optimal.

For example, if the cards are arranged as [1, 2, 100, 3], it might seem better to take 3 from the right end rather than 1 from the left end, but doing so would allow the opponent to take 100, potentially worsening the score difference.

In situations like this where “both players play optimally,” dynamic programming (DP) is effective. In particular, interval DP can be applied.

A naive brute-force search has the choice of picking left or right at each turn, resulting in up to \(2^N\) possible choices, which would cause TLE. Given the constraint \(N \leq 3000\), we need to reduce the computational complexity.

Therefore, we use interval DP to precompute, for the interval [i, j] of remaining cards, “the score difference that the current player can ultimately achieve.”

Algorithm

We use interval DP. The DP table is defined as follows:

\(DP[i][j]\) := When the remaining cards are from the \(i\)-th to the \(j\)-th, the maximum value of the score difference (current player’s score − opponent’s score) that the current player can achieve

Initial condition: - When only one card remains, taking that card is optimal, so: $\(DP[i][i] = V[i]\)$

Transition: - When multiple cards remain, the current player can choose either the left end or the right end. - If the left end is chosen: - The player gains \(V[i]\) points, and then it becomes the opponent’s turn on the interval \([i+1, j]\), so we need to subtract \(DP[i+1][j]\), which is the score difference when the opponent plays optimally. - The score difference is \(V[i] - DP[i+1][j]\) - Similarly, if the right end is chosen: - The score difference is \(V[j] - DP[i][j-1]\)

Therefore, the transition formula is: $\( DP[i][j] = \max(V[i] - DP[i+1][j],\ V[j] - DP[i][j-1]) \)$

Finally, what we want is Takahashi’s score difference for the initial interval \([0, N-1]\), so we output: $\( DP[0][N-1] \)$

Example

Sample input:

4
1 2 100 3

Through the DP table update process, \(DP[0][3]\) is ultimately computed as Takahashi’s score difference.

Complexity

• Time complexity: \(O(N^2)\)
• Space complexity: \(O(N^2)\)

Since each interval is computed exactly once, the time complexity is quadratic. The space usage is also quadratic due to the table.

Implementation Notes

• Pay attention to the update order of the DP table. You need to update from shorter intervals to longer intervals.

• Initialization is done for single-card intervals, and then intervals of length 2 or more are processed.

• The key point is that we subtract the opponent’s optimal value when computing transitions (because we are considering score differences).

  Source Code

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    V = list(map(int, data[1:N+1]))
    
    # DP[i][j] := 残っているカードが i 番目から j 番目までのとき、
    # その時の手番の人が最終的な得点差（現在の手番の人 - 相手）を最大化したときの値
    DP = [[0]*N for _ in range(N)]
    
    # 初期化: 残るカードが1枚のとき
    for i in range(N):
        DP[i][i] = V[i]
    
    # 区間DP: len が 2 以上の場合
    for length in range(2, N+1):       # length はカードの枚数
        for i in range(N - length + 1):
            j = i + length - 1
            # 左端を取る場合：V[i] を得て、次の相手の最適解を引く
            left_choice = V[i] - DP[i+1][j]
            # 右端を取る場合：V[j] を得て、次の相手の最適解を引く
            right_choice = V[j] - DP[i][j-1]
            DP[i][j] = max(left_choice, right_choice)
    
    print(DP[0][N-1])

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.