EDPC L - Deque

考え方

ABCでいうと、E問題級。

値というよりは範囲を広げていく動的計画法、通称区間 DP。
といっても、そこまで特殊な考えなわけではない。
左端と右端の位置を使った $2$ 次元の動的計画法で、初期値を入れる場所と継承の方向が少し独特なだけ。

まず、問題を少しわかりやすく言い換える。
太郎君は $X-Y$ を最大化しようとし、次郎君は最小化する、とあるが、これはわかりにくい。
太郎君は $X-Y$ を最大化しようとし、次郎君は $Y-X$ を最大化しようとする、の方がよい。

なぜなら、その変更によって、単純な対戦ゲームになるから。
各局面で、自分の全行動について「その行動で得る点 $-$ その後の最善手での結果」を求めればよい。
採用するのは、そのうちの最大値である。

終了パターンがある程度限られることもあり、バックトレースで考えることになる。

あとは、これをコードにすればよい。

計算量は $O(N^2)$。

入力例1での動作

入力を受け取る。

n: 4
a: {10, 80, 90, 30}

dp[l][r] を、区間 a[l] から a[r] までが残っているときの、
現在の手番の人の得点 $-$ 相手の得点の最大値とする。

最初に、次のように初期化する。
残り $1$ つの場合、それを取るしか選択肢がないので、その得点がそのまま最大値になる。

次に、たとえば dp[2][3] を考える。
このマスは、{90, 30} という状態での先手の得点予測である。

左端から取る場合、まず自分に $90$ 点入る。
その後の展開は、下のマスを見れば、相手の方が $30$ 点多くなる展開が予測できる。
つまり、左端から取った場合の得点予測は $60$ 点となる。

同様に、右端から取る場合、自分に $30$ 点、その後相手が $90$ 点多く取るので、得点予測は $-60$ 点となる。
よって、多い方を考えて、ここの得点予測は $60$ 点となる。

dp[2][3] = max(90 - dp[3][3], 30 - dp[2][2])
         = max(60, -60)
         = 60

この提出コードでは、表の下段から順に、左から埋めていく。
具体的には、次の順に値が確定する。

dp[2][3]
dp[1][2] -> dp[1][3]
dp[0][1] -> dp[0][2] -> dp[0][3]

実際に埋めると、次のようになる。

右上の $10$ が答えである。
左下部分はメモリが無駄になるので、実務だったらちょっと考えないといけないが、競プロなら関係ない。

注意点

答えは、int 型からはみ出る。
DP テーブルを含め、long long 型を用いること。

別解

特になし。