DP俯瞰?
他のDPの記事
http://d.hatena.ne.jp/Tayama/20111210/1323502092
http://d.hatena.ne.jp/komiyam/20111212/1323615687
Typical DP Contest
http://tdpc.contest.atcoder.jp/
- 基本(1)
- フィボナッチ数列
- 一次元累和
- パスカルの三角形
- 多次元累和
- 二次元はセル(x,y)に(i,j)(i<=x, j<=y)の総和が入っている
- その他問題
- 基本(2)(有名問題)
- 最長共通部分列問題(LCS)
- 編集距離問題
- 最長増加部分列問題(LIS)
- 硬貨両替問題
- 硬貨が1,3,4円だったときにn円で必要な最小枚数を求める問題を指す
- 最短経路問題?
- Bellman-ford法
- Warshall-Floyd法
- 問題を解くときに前計算として使う場合がよくある
- ある特定の頂点のみを経由する最短経路を使用する問題
- bitDP
- 巡回セールスマン問題
- 漸化式がdp[S] = min(dp[T] + dp[U] + f(S,T,U)) ( T,U \subset S, T and U = empty ) (パッと見O(4^n)かかるがO(3^n)で済む形)
- いくつかの状態を確定したら残りの部分はgreedyで確定するもの
- ドミノ敷き詰め問題
- connectedな情報をプラスして持つbitDP
- 木DP
- 木の直径
- (問題)
- comittee(JOI 春合宿2008)
- Distribution(JOI 春合宿2009)
- MultiEndingStory( AOJ2344 )(難)
- 区間DP
- 蟻本のBribe the Prisonersなど、大概O(N^3)
- Monge性を持たせて高速化O(N^2)
- 最適二分探索木問題
- 区間+もうひとつの情報でO(N^5)->O(N^4)の高速化 : SRM492D1Med, SRM499D1Med
- 確率DP
- 桁DP(DigitDP)
- 1<=x<=10^100で...を満たすものは何通りあるか(mod 10^9+9) 系
- ....の性質を満たすようなx番目の数を答えよ 系
- 累和を用いるDP
- 累和で得た結果を中心に使う問題
- JOI2010本選1, Uva108, APIO2009 Oil
- 累和を使う高速化
- imos法(累和の逆演算)
- Nails(2012JOI本選4), Pyramid(AutumnFest2012)
- 累和で得た結果を中心に使う問題
- BITやsegmentTreeと組み合わせるDP
- 行列累乗(二乗反復)
- 基本は蟻本がくわしい, O(N^3 log k)
- (E+A+A^2+..+A^k)を求めるもの
- 上三角/下三角テプリッツ行列, O(N^2 log k)
- 巡回行列, O(N^2 log k)
- その他
- ある種の完全マッチングの数え上げ
- AOJ2439 hakone
- SRM592Div1 Medium
- SRM489Div1 Medium も似ている
- ある種の極大となるものの数え上げ
- AOJ2333 僕の友達は小さい
- JOI 2012合宿 Day3 Kangaroo
- 最大の矩形の探索
- 壁セルがある時に作れる最大長方形(DPは嘘かもしれない) http://algorithms.blog55.fc2.com/blog-entry-133.html
- 壁セルがあるときに作れる最大正方形 http://algorithms.blog55.fc2.com/blog-entry-131.html
- ある種の完全マッチングの数え上げ
追記
