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

hamayanhamayan's blog

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

区間DP

dp[L][R] := 区間[L,R]についての何か
簡単な入門問題があまりなかったですね

問題

Codeforces Tinkoff Challenge - Elimination Round D. Presents in Bankopolis

http://codeforces.com/contest/793/problem/D

Typical DP Contest I. イウィ

http://tdpc.contest.atcoder.jp/tasks/tdpc_iwi

yukicoder No.484 収穫

https://yukicoder.me/problems/no/484

[難] CODE FESTIVAL 2015 決勝 G. スタンプラリー

http://code-festival-2015-final-open.contest.atcoder.jp/tasks/codefestival_2015_final_g


以下、短い解説。

Codeforces Tinkoff Challenge - Elimination Round D. Presents in Bankopolis

http://codeforces.com/contest/793/submission/26633764
dp[L][R][cnt][isRight] := [L,R]の区間で左右どちらか(isRight)にいるとき、cnt頂点分移動するのにかかる最小コスト

IPCP国内予選2016 D. ダルマ落とし

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の区間で消せる回数の最大数
イウィと全く同じ

Typical DP Contest I. イウィ

http://tdpc.contest.atcoder.jp/tasks/tdpc_iwi
2回区間DPする
dp[L][R] := L~Rの区間を全部消せるか
dp2[L][R] := L~Rの区間で消せる回数の最大数

AOJ 0303 力持ち

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0303
dp[L][R] := L~Rの区間で一番下が1人になれるかどうか
dp2[L][R] := L~Rの区間で一番下で歩く最小人数

AOJ 0615 ケーキの切り分け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)ときの最短時刻
区間がまだ処理していないという所が面白い