はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおける区間DP問題まとめ

区間DP

解法メモ(全部じゃない)

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)ときの最短時刻
区間がまだ処理していないという所が面白い