https://atcoder.jp/contests/joi2015ho/submissions/15037441
https://atcoder.jp/contests/joi2015ho/submissions/15727225
- 循環バッファはサイズを余分に持つと実装がシンプルになる
- 区間DPは逆順に処理しても同値というテクニックが使える場合がある
- 初期値は if (N % 2 != 0) rep(i, 0, 2 * N) dp[i][i] = A[i];
- 繰り返しは rep(range, 1, N) rep(l, 0, 2 * N)
- 更新は if (count % 2 != 0) dp[l][r] = max({ dp[l][r - 1] + A[r], dp[l + 1][r] + A[l] });
- 出力は rep(l, 0, N) ans = max(ans, dp[l][l + N - 1]);
- 区間DPで2Nまで用意したら区間左端を2Nまで動かして更新すること
- 出力も区間左側を2Nまで動かしてmaxを取ること
- 追記 半開区間の実装も提出した
組み合わせが非常に多いのでメモ化したい、つまり区間DPをする。既にケーキを取った区間を[l, r]とすると、[l+1, r]状態からcake[l]を取るか、[l, r-1]状態からcake[r]を取るか、2通りの遷移が考えられる。「無になるまでケーキを取る」と「無からケーキを構築する」は最終結果を考えれば同値となるので、後者の方針で実装する。dp[l][r] := 閉区間[l,r]からJOIが取ったケーキの最大値 とすると
ケーキを構築するのがJOIのとき
if (count % 2 != 0) dp[l][r] = max({ dp[l][r - 1] + A[r], dp[l + 1][r] + A[l] });
ケーキを構築するのがIOIのとき
if (A[l] < A[r]) dp[l][r] = dp[l][r - 1];
else dp[l][r] = dp[l + 1][r];
初手の構築がJOIかIOIかケーキ全体のサイズで決まる。あとは2の剰余で上記を交互に処理していけば求まる。なお、循環バッファは2倍のサイズにすると実装がシンプルになる。計算量はになる。
