Deque [Educational DP Contest / DP まとめコンテスト L]

https://atcoder.jp/contests/dp/tasks/dp_l

前提知識

• ミニマックス法
• 区間DP

解説

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

問題設定がミニマックス法に適しているので適用する。
DPコンテストなのだが、区間DPなので、メモ化再帰で書いている。
（自分は区間DPはメモ化再帰で書くほうが多い）
状態にどちらのターンかを含めてもいいが、減量diffの偶奇で分かるので、含めていない。
遷移先はどちらの端を取るかの二択。

int N; ll A[3010];
//---------------------------------------------------------------------------------------------------
int vis[3010][3010];
ll memo[3010][3010];
ll dp(int L, int R) {
    if (L > R) return 0;
    if (vis[L][R]) return memo[L][R];
    vis[L][R] = 1;
 
    int diff = N - (R - L + 1);
 
    ll res = 0;
    if (diff % 2 == 0) {
        // X-Yを最大化したい
        res = -infl;
        chmax(res, dp(L + 1, R) + A[L]);
        chmax(res, dp(L, R - 1) + A[R]);
    } else {
        // X-Yを最小化したい
        res = infl;
        chmin(res, dp(L + 1, R) - A[L]);
        chmin(res, dp(L, R - 1) - A[R]);
    }
 
    return memo[L][R] = res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
 
    cout << dp(0, N - 1) << endl;
}