AtCoder Beginner Contest 128：D - equeue
問題
解法
問題文中の４つの操作は以下のように言い換えられる：
操作①：左端の宝石を捨てるが，最後に元に戻す
操作②：左端の宝石を捨てる，一生もとに戻さない
操作③：右端の宝石を捨てるが，最後に元に戻す
操作④：右端の宝石を捨てる，一生もとに戻さない
この４つの新しく作った操作を遷移とする DP を考える：
dp(l, r, l) := 区間 [l, r] にあと最大 k 回操作できるとき，得られる価値の和の最大値
とおくと，
res1 = dp(l + 1, r, k - 1) + V[l]
res2 = dp(l + 1, r, k - 2)
res3 = dp(l, r - 1, k - 1) + V[r]
res4 = dp(l, r - 1, k - 2)
とする．res1 は操作①，res2 は操作②，res3 は操作③，res4 は操作④に対応している．このとき，
dp(l, r, k) = min(res1, res2, res3, res4, 0)
で更新できる．最後の 0 はこれ以上操作をしないことを表している．[l, r] の幅が 1 になったときは取るか取らないかの２択になることに注意する．O(N^2 * K)．
解答
