Submission #24428557

---

Source Code Expand

import sys

def main(f):
  N = int(f.readline())
  A = [None] + list(map(int, f.readline().split()))

  # N は偶数と仮定する
  dp = [[None] * (N+1) for _ in range(N+1)] # dp[i][j] : 残りが a_i ... a_j の時の状態価値関数、つまり、この後に X-Y に追加できる値
  for i in range(1, N+1): # 幅 d = 1 の場合
    dp[i][i] = -A[i]

  for d in range(2, N+1):
    for i in range(1, N-d+2):
      j = i + d - 1
      if d % 2 == 0:
        case_l = A[i] + dp[i+1][j]
        case_r = A[j] + dp[i][j-1]
        dp[i][j] = max(case_l, case_r)
      else:
        case_l = -A[i] + dp[i+1][j]
        case_r = -A[j] + dp[i][j-1]
        dp[i][j] = min(case_l, case_r)

  if N % 2 == 0:
    print(dp[1][N])
  else: # N が奇数だった場合は符号違いを答えればよい
    print(-dp[1][N])

main(sys.stdin)

Submission Info

Judge Result