AtCoder Educational DP Contest L問題解いてみた

今回の問題

問題文

太郎君と次郎君が次のゲームで勝負します。
最初に、数列 $a=(a_1, a_2, \ldots, a_N)$ が与えられます。
$a$ が空になるまで、二人は次の操作を交互に行います。先手は太郎君です。

• $a$ の先頭要素または末尾要素を取り除く。
• 取り除いた要素を $x$ とすると、操作を行った人は $x$ 点を得る。

ゲーム終了時の太郎君の総得点を $X$、次郎君の総得点を $Y$ とします。
太郎君は $X - Y$ を最大化しようとし、次郎君は $X - Y$ を最小化しようとします。

二人が最適に行動すると仮定したとき、$X - Y$ を求めてください。

制約

• 入力はすべて整数である。
• $1 \leq N \leq 3000$
• $1 \leq a_i \leq 10^9$

自分の回答

#include <bits/stdc++.h>
#include <atcoder/dsu>
using namespace std;
using namespace atcoder;
int main() {
    int n;
    cin >> n;
    int alist[n];
    for (int i = 0; i < n; i++) {
        cin >> alist[i];
    }
    long long dp[n + 1][n + 1];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            dp[i][j] = 0;
        }
    }
    for(int len = 1; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            if (len == 1) {
                dp[i][j] = alist[i];
            } else {
                dp[i][j] = max(alist[i] - dp[i + 1][j], alist[j] - dp[i][j - 1]);
            }
        }
    }
    cout << dp[0][n - 1] << endl;
    
    return 0;
}

解説

問題文からはわかりにくいがどちらも自分の得点-相手の得点を大きくしようとしている。dp[l][r]をl~rまで残った時の自分が手番だった時の理論値とする。区間が狭いところから順に探索を行っていく。ある区間ijはi+1,jかi,j-1から遷移することにより、漸化式が立てられ解くことができる。

初見だと絶対無理、、、（ｄｐのほとんどの問題は最初できない、、、）