区間DP
- dp[L][R] := 区間[L,R]についての何か
- 簡単な入門問題があまりなかった
- 発展的だが、Monge性を利用して更新高速化できる場合がある
- 区間DPのよくある方針としてdp[L][R]をdp[L+1][R]とdp[L][R-1]を使って更新する方針がある
- 【テク1】中心が決まっていて、左右に遷移区間を伸ばす場合は、左と右の遷移を別々にカウントして、掛け合わせることでO(N)分節約可能
問題
- EDPC Slimes 解説
- CC Algebra Score 解説
- LC Minimum Cost Tree From Leaf Values
- CF XOR-pyramid
- CF Presents in Bankopolis
- AOJ ダルマ落とし
- AtCoder イウィ
- AOJ 力持ち 解説
- AOJ ケーキの切り分け2
- yukicoder No.484 収穫
- AGC020 Encoding Subsets 解説 区間DPっぽい感じだがもうちょっと状態数が増える
- AOJ 塗り箸 (Chopsticks)
- CF505 Disjoint Triangles 解説
- CF538 Flood Fill 解説
- 区間DPで回文を扱う問題が結構ある
- 【テク1】CGR4 F1 Short Colorful Strip
ここから結構難しい
解法メモ(全部じゃない)
CF Presents in Bankopolis
http://codeforces.com/contest/793/submission/26633764
dp[L][R][cnt][isRight] := [L,R]の区間で左右どちらか(isRight)にいるとき、cnt頂点分移動するのにかかる最小コスト
AOJ ダルマ落とし
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1611&lang=jp
これも2回区間DPする
dp[L][R] := L~Rの区間を全部消せるか
dp2[L][R] := L~Rの区間で消せる回数の最大数
イウィと全く同じ
AtCoder イウィ
http://tdpc.contest.atcoder.jp/tasks/tdpc_iwi
2回区間DPする
dp[L][R] := L~Rの区間を全部消せるか
dp2[L][R] := L~Rの区間で消せる回数の最大数
AOJ 力持ち
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0303
dp[L][R] := L~Rの区間で一番下が1人になれるかどうか
dp2[L][R] := L~Rの区間で一番下で歩く最小人数
AOJ ケーキの切り分け2
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0615
環状じゃなかったら入門形
dp[L][R] := L~Rの区間でJOIくんが取れるピースの大きさの合計の最大値
yukicoder No.484 収穫
https://yukicoder.me/problems/no/484
dp[isright][L][R] := 区間[L,R]が"未"収穫で今左右のどちらかにいる(isright)ときの最短時刻
区間がまだ処理していないという所が面白い