公開日 :
更新日 :

状態を持つDP(dp[i][状態])

「先頭から\(1\)つずつ選んでいく。でも、次の選択に影響するのは直前のちょっとした情報だけ」という問題を、 dp[i][状態] で解くDP。
全部の選び方(\(2^N\)や\(3^N\))を調べる代わりに、「\(i\)番目まで決めて、いま状態\(s\)である」ものを\(1\)つにまとめる。
計算量は N × 状態数 × 遷移の数。

使える問題の目印

  • 各要素について少ない選択肢から\(1\)つ選ぶ(反転する/しない、表/裏、グー/チョキ/パー、食べる/食べる)。
  • 得点や条件が隣どうし(または直前の数個)だけ決まる。
    • 「\(i\) と \(i+1\) が ◯◯ なら \(+Y\)」「隣と同じではいけない」「連続\(K\)回までならOK」
  • 「お腹を壊している」「区間の中にいる」のようなモードがある。
  • \(N\) が \(2\times 10^5\) くらいで、全探索は無理。

コードを書く前に決める4つ

決めること例(ABC464 Dの場合)
【状態】 次の選択・得点に必要な「過去の情報」は何かi 日目の最終的な天気(S/R)の2通り
【遷移】 状態 p から、今回 c を選ぶと何点増える/減るか。
選べない組はどれか。
前日 R → 今日 S なら \(+Y\)。
元の天気と違えば \(-X\)
【初期値】 1個目(または0個目)の値1日目を S/R にするコスト
【答え】 最後にどの状態を見るかS/R の大きい方

【状態】が一番大事。
考え方は「i+1番目以降を決めるときに、i番目までについて何を知っていれば十分か?」。
それ以外の過去の情報は捨ててよい。
したがって、同じ状態のものは「一番いいもの」だけ残せばよい。

状態の種類

種類状態大きさ例
直前の選択直前の要素で何を選んだか選択肢の数ABC464 D(天気 2)、
ABC291 D(表/裏 2)、
ABC365 D(手 3)、
ABC242 C(数字 9)
モードお腹の調子、持っているか など\(2\sim 3\)ABC306 D(元気/お腹を壊している)
区間の前・中・後「1つの区間を選んで操作」のどこにいるか\(3\)区間を \(1\) つ選んで反転・\(2\) 倍にするなど
連続回数同じものが今何回続いているか\(K+1\)「同じ文字は \(K\) 回まで連続OK」
偶奇・余り個数や和の modmod の大きさ「選んだ個数が偶数」
tightN をなぞているか2桁DP