考察
円上の塗り上書きは履歴が複雑だが、逆順なら「区間内が0または色cのとき、全て0へ消す」操作に変えられる。費用は区間長+X_c。前向きで後の塗りに隠れたマスを0というwildcardにしておくためである。正の費用なので、消去区間の両端が0なら縮めてよく、両端は元の色cが残る形にできる。
Cを二周へ複製し、半開区間[l,r)の完全消去費用をdp[l][r]とする。補助ep[l][r]は、左端lを消さず、区間内を0またはC_lだけにする最小費用である。残すC_lの位置は自由に選び、他の色は全て消す。この「左端を残す」が固定費を最後に一度だけ払う状態の境界条件になる。
dp[l][l]=ep[l][l]=0、非空区間は∞で初期化し、長さ1,…,Nの昇順に次を計算する。空epは一文字を残す遷移の便宜上の基底であり、C_lへの参照は非空区間だけで行う。
for length = 1,...,N:
for [l,r) within the doubled array with r-l = length:
for m = l+1,...,r-1:
dp[l][r] = min(dp[l][r], dp[l][m] + dp[m][r])
ep[l][r] = min(ep[l][r], ep[l][m] + dp[m][r])
if C[l] == C[r-1]:
ep[l][r] = min(ep[l][r], ep[l][r-1])
dp[l][r] = min(dp[l][r], ep[l][r] + length + X[C[l]])
answer = min(dp[i][i+N] for i = 0,...,N-1)
epの二遷移は、右端を消す場合と右端をC_lのまま残す場合である。前者では最後に残すC_lより右をdpで消し、後者では右端を何もせず足す。dpは独立な二区間への分割と、全区間を最後の一操作で消す候補を比べる。全区間消去候補は両端の元色が同じ時に用い、epを先に確定させる。一文字ではep=0、dp=1+X_{C_l}になる。
例えばC=(1,2,1)なら中央を1+X_2で消し、全体を3+X_1で消すことで色1の固定費を共有できる。色ごとの連続区間を独立に塗るgreedyでは、この離れた同色をまとめる利得を表せない。
典型の発動条件
操作の逆転とinterval DP
発動条件: 上書き操作の最後の作用範囲がsubproblemを分離するとき。
逆向きの消去として最後のintervalで分割する。
circular interval DP
発動条件: 円環のcut位置が最適解に依存するとき。
列を二倍して全長N interval開始を試す。
問題固有の要素
固定費X_cのため異色部分を先に0へ消せば、最後のc操作でそれらを跨いで一括消去できることをepが表す。
別の問題へ持ち帰る視点: range overwrite最小costは逆操作でwildcard/emptyを許すinterval grammarへ変換する。
正当性
前向き塗り列を逆順に見ると、その操作で最終色が確定したマスはcで、後の操作に隠れるマスは既に0である。従って合法な消去列が得られる。逆に消去列を反転して同じ区間をcで塗れば、消去で0だったマスは後の塗りに上書きされ、各マスの目標色を復元する。最適値は同じである。
消去は色を0にするだけなので、最後に消す区間の両端cは、それまで一度も消されていない。両端を跨ぐ先行消去はこのcを消してしまうため存在せず、最後の区間の内部と外部は独立である。線形区間で最後の操作が全区間でなければ、その区間端の少なくとも一方で二つへ切れる。全区間なら両端がC_lであり、前処理は左端を残して0またはC_lへするepである。
epでは右端が残るなら元色がC_lで、短いepへ無料で付け足せる。消えるなら最後に残すC_lの直後で切り、左のepと右のdpへ分けられる。残る左端が先行操作を跨がせないためこの分割も独立である。長さに関する帰納法で二表の遷移は全最適消去列を表す。円でも最後の消去区間の境界をcutに取ると、それ以前の操作はその境界を跨がず線形解になる。全cutの最小が円の最適値に一致する。
実装上の注意
- 半開区間と長さr−lを統一する。epの左端を残す意味を保ち、C_l=C_{r−1}の分岐を明示する。
- 同じ区間のepを確定してから全区間消去候補をdpへ入れる。全分割先は短い区間なので長さ昇順でよい。
- 二重列の長さN以下だけを計算する。X_i≤10^9で総費用は32 bitを超えるので64 bit整数を使う。
復習の核
- N≤7で操作区間・色をbounded BFSし、同色が離れて現れるcase、全同色、cutを跨ぐ最適操作をDPと比較する。
計算量と制約
時間
円周 N 点。二重列の長さ≤N区間は O(N²)、各区間に O(N) 分割を試すため O(N³)。
空間
dp と補助 ep の区間表で O(N²)。
制約との対応
公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 400; 1 \leq C_i \leq N; 1 \leq X_i \leq 10^9; All input values are integers.
出典