EDPC L - Deque

考え方

ABCでいうと、E問題級。

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

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

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

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

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

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

入力例1での動作

入力を受け取る。

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

残っている区間ごとに、現在の手番の人の得点 $-$ 相手の得点の最大値を考える。

残りが $1$ つなら、それを取るしかない。
そのため、その値がそのまま得点差になる。

まず、$\{90,30\}$ が残っている場合を考える。

左端の $90$ を取ると、その後は相手が $30$ を取る。
この場合の得点差は $90-30=60$ である。

右端の $30$ を取ると、その後は相手が $90$ を取る。
この場合の得点差は $30-90=-60$ である。

大きい方を選ぶので、$\{90,30\}$ の得点差は $60$ となる。

次に、$\{80,90,30\}$ が残っている場合を考える。

左端の $80$ を取ると、残りは $\{90,30\}$ になる。
この区間では、次の手番の人が $60$ 点多く取れる。
したがって、今回の手番から見た得点差は $80-60=20$ である。

右端の $30$ を取ると、残りは $\{80,90\}$ になる。
この区間では、次の手番の人が $10$ 点多く取れる。
したがって、今回の手番から見た得点差は $30-10=20$ である。

どちらを選んでも $20$ なので、$\{80,90,30\}$ の得点差は $20$ となる。

同じ考え方で全ての区間を求めると、次の表になる。

全体 $\{10,80,90,30\}$ の得点差は $10$ である。
したがって、答えは $10$。

注意点

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

別解

特になし。