B - ケーキの切り分け２ (python)

区間dp の問題。区間dp とは、dp[ i ][ i+j ] = list[ i : i+j ] での最大(最小)値として、最大値の遷移を考えるもの。
今回は、dp[ i ][ j ] = ケーキが i+1 番から i+j+1 番まで残っているときの JOI 君の取り分の最大値
として問題を解く。
ケーキが円状で、1番とN番が続いているのを考慮する必要がある。対策としては二つあり、
１．ケーキの番号を2周分持つ。（N-1番から2番までのケーキを考えたいときは、N-1番からN+2番までのケーキがあるとして dp を作る。）
２．i → j は必ず左回りにケーキが続いている状態と定義する。（ i = 2, j = N-1 なら、2,3,...N-1番までのケーキが残っている状態、i = N-1, j = 2 なら N-1,N,1,2 のケーキが残っている状態）
また遷移の仕方は
残っているケーキが j+1 個だとすると、N - ( j+1 ) が偶数なら JOI 君のターンなので
dp[ i ][ i+j ] = max( dp[ i+1 ][ i+j ] + A[ i ], dp[ i ][ i+j-1 ] + A[ j ] )
奇数なら IOIちゃんのターンで、IOI ちゃんは両端のうち大きい方を取るので、
dp[ i ][ i+j ] = dp[ i+1 ][ i+j ] if A[ i ] > A[ j ] else dp[ i ][ i+j-1 ]
となります。
計算量は１が O(4*n**2), ２が O(n**2)

# 1
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n = int(readline())
a = [int(readline()) for i in range(n)]
if n == 1:
  print(a[0])
  exit()
  
dp = [[0]*(2*n) for i in range(2*n)] #2周分
if n%2 == 1: #最後の１つを JOI 君が取るなら加算
  for i in range(2*n):
    dp[i][i] = a[i%n]

for i in range(1,n):
  for L in range(2*n-2-i):
    R = L+i # L が左端 R が右端
    if (n-(i+1))%2 == 1:
      dp[L][R] = dp[L][R-1] if a[R%n] > a[L%n] else dp[L+1][R]
    else:
      dp[L][R] = max(dp[L][R-1]+a[R%n], dp[L+1][R]+a[L%n])
  
ans = 0
for i in range(n):
  ans = max(ans, dp[i][i+n-1])
print(ans)

# 2
import sys
input=sys.stdin.readline

n = int(input())
a = [int(input()) for i in range(n)]

dp = [[0]*n for i in range(n)] # 1周分
for i in range(n):
  for L in range(n):
    R = (L+i)%n
    if (n-(i+1))%2 == 1:
      dp[L][R] = dp[(L+1)%n][R] if a[L] > a[R] else dp[L][(R-1)%n]
    else:
      dp[L][R] = max(dp[(L+1)%n][R]+a[L], dp[L][(R-1)%n]+a[R])
      
ans = 0
for i in range(n):
    ans = max(ans, dp[i][i-1])
print(ans)