Educational DP Contest / DP まとめコンテスト [ L - Deque ] https://atcoder.jp/contests/dp/tasks/dp_l

edpc_l.py

'''
[問題]
https://atcoder.jp/contests/dp/tasks/dp_l

[解説]
https://kyopro-friends.hatenablog.com/entry/2019/01/12/231000
 dp[i][j]=(区間[i,j]が残ってるときの「次の手番の人の得点－そうじゃない方の人の得点」)
 とすればよさそうだね。実装はメモ化再帰が簡単かな。
 計算量はO(N^2)

https://blog.hamayanhamayan.com/entry/2019/01/09/004223
 問題設定がミニマックス法に適しているので適用する。
 DPコンテストなのだが、区間DPなので、メモ化再帰で書いている。

[参考]
https://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%8B%E3%83%9E%E3%83%83%E3%82%AF%E3%82%B9%E6%B3%95
　ミニマックス法（みにまっくすほう、英: minimax）またはミニマックス探索とは、想定される最大の損害が最小になるように決断を行う戦略のこと。

メモ化再帰ちょっと理解した
https://sarashina-nikki65.hatenablog.com/entry/2018/10/11/163203
　メモ化再帰って、計算済みパラメータの再帰関数呼び出しをキャッシュしとくって意味か。

区間DP の考え方と使える状況まとめ
https://algo-logic.info/range-dp/
区間DPとは、区間を表す添え字を持つ動的計画法(DP)のことです。
𝑑𝑝[𝑙][𝑟] := 区間 [ l, r ) について、最適な状況下での何かしらの値

https://atcoder.jp/contests/dp/submissions/24720812

[結果]
Python(3.8.2) TLE
PyPy3(7.3.0) AC 273ms
'''

import sys

sys.setrecursionlimit(10 ** 6)  # 再帰上限の引き上げ
input = sys.stdin.readline

INF = 2 ** 63 - 1

N = int(input())
A = list(map(int, input().split()))

# 𝑑𝑝[𝑙][𝑟] := 区間 [ l, r ) について、二人が最適に行動すると仮定したとき、X − Yの値
dp = [[0] * (N + 1) for i in range(N + 1)]

# Wはwidth、幅のW
for W in range(N):
    # 幅がWなので、LのループはN-Wまで
    #
    # L, Rの値は0, 0から始まって、Lが終点まで行ったら、0, 1(Wが1に)
    # 最終ループでWがNになり、dp[0][N-1]の値が計算される
    for L in range(N - W):

        # 幅がWなんで、右端RはL + W
        R = L + W

        # 先攻後攻の判定
        # 先行1回目は、Nに対して、W = N-1
        # なのでW%2 != N%2のとき、先行
        if W % 2 != N % 2:
            # X - Y を最大化しようとする
            # L - R間でベストな方の値をdp[L][R]に入れる
            dp[L][R] = max(dp[L + 1][R] + A[L], dp[L][R - 1] + A[R])
        else:
            # X - Y を最小化しようとする
            # L - R間でベストな方の値をdp[L][R]に入れる
            dp[L][R] = min(dp[L + 1][R] - A[L], dp[L][R - 1] - A[R])

        # dbgout
        #print(L, R, dp[0][N-1])

# 0スタートなんでN-1まで
print(dp[0][N-1])