公開日 :
更新日 :
「先頭から\(1\)つずつ選んでいく。でも、次の選択に影響するのは直前のちょっとした情報だけ」という問題を、 dp[i][状態] で解くDP。
全部の選び方(\(2^N\)や\(3^N\))を調べる代わりに、「\(i\)番目まで決めて、いま状態\(s\)である」ものを\(1\)つにまとめる。
計算量は N × 状態数 × 遷移の数。
| 決めること | 例(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」 |
| 偶奇・余り | 個数や和の mod | mod の大きさ | 「選んだ個数が偶数」 |
| tight | N をなぞているか | 2 | 桁DP |