動的計画法更新最適化？
- セグメント木や累積和
- 行列累乗
- DPの更新式を見てみると、一回の更新操作が行列の形になるときがある
- この場合は行列を繰り返し二乗法の要領でN乗しておくことで、N番目の要素を高速に取り出せる。
- Convex Hull Trick
- 関数の形式になっている区間最小値を素早く見つける手法 参考1 参考2
- わかりやすい資料
- dp[i] = min{j=0...i-1}（dp[j] + A[i] * B[j])
- dp[i] = (iの関数) + min{j=0...i-1}（（jの関数)*i+(jの関数))
- addは昇順に行う必要がある
- addがどんな順番でもいい、動的CHTもある 日本語資料 資料
- 完全永続CHTの資料
- CFでdel操作について言及がある
- 最近のトレンド「Li Chao Segment Tree」
- （DP高速化問題ではないが）CHTをうまく改変して解く問題
- 分割統治
- 「A[i][j] := dp[i][j]の更新に必要なk」と定義したときにA[i][j] <= A[i][k] (j < k)であるときに使える。
- dp[N][M]の計算がO(NM^2)からO(NMlogM)にできる
- イメージ的にはこの資料の36ページからの問題、説明はここのFの解説が分かりやすい
- どういう場合にA[i][j] ≦ A[i][k]といえるのかがまだ分かってない（Monge性+単調性があると言える？）
- 条件に関するメモ
- C[i][j]を高速に求める部分が少し大変だが、式の変形でO(1)にできる場合と尺取法の様なやり方を取ることでならしO(1)にできる場合とがある
- 備忘録
- MongeDP
- AlienDP (trick from Aliens)
- かなりよく分かってないので、誰か解説記事を書いて欲しい。以下のまとめは責任持てない
- CSA Or Problemで見た
- ここの議論を見た感じ…
- 「f(j) = dp[i][j]」としたときに「f(j + 1) - f(j)≦f(j) - f(j - 1)」を満たす必要がある
- Swistakk氏はこれをconvexity(凸包性)と呼んでた（しかもeditorialで証明できてなかったからしてた）
- 分割統治、CHTの特殊パターン？
- 解説記事
- 名付け親の問題 Alien ちょっとした解説
- 数学的なバックであるラグランジュ緩和
- 勝手にリンクを張るけどプロからのありがたいヒント その1 その2
- AlienDP使える問題？ 解説
- 問題
- インラインDP
- skyさんによる素晴らしい記事
- DPで2次元配列となるが、遷移が単純なので、普通なら空間O(NM),計算量O(NM)かかる所を、セグメントツリー全体をDPの配列として更新していくことで、空間O(N),計算量O(MlogN)で済むテク
- 普通の配列でやるインラインDPもある。入門的。DPをするときのメモリ節約術を思い立たせる
- 名前が無いのでここに追加するのに困っていたが、インラインDPという名前はとても良いと思う（なんとなくかっこいいので）
- きたまさ法
問題
セグメントツリーや累積和
- EDPC Candies 解説
- EDPC Permutation 解説
- yukicoder No.844 split game 解説
- yukicoder No.1011 Infinite Stairs 解説
- http://codeforces.com/blog/entry/22616 のSegment Tree & Dp
- CF426 The Bakery (区間add, 区間maxの遅延評価セグメントツリー)
- EDPC Intervals 解説 (区間add, 区間maxの遅延評価セグメントツリー)
- HR Matrix Land (単一更新, 区間maxのセグメントツリー) 解説
- yukicoder No.704 ゴミ拾い Medium 解説
- AC Neutralize 解説
- AC 通勤 解説
- yukicoder No.777 再帰的ケーキ 解説
- AGC031 Reversi 解説
- yukicoder No.801 エレベーター 解説
行列累乗
- フィボナッチ数列を行列累乗で求めるやつが有名
- EDPC Walk 解説
- AOJ One-Dimensional Cellular Automaton
- yukicoder No.840 ほむほむほむら 解説
- AtCoder 家
- CF420 Okabe and El Psy Kongroo
- yukicoder No.541 3 x N グリッド上のサイクルの個数
- yukicoder No.569 3 x N グリッドのパスの数 解説
- HOJ devilswalk 解説
- AOJ Almost Infinite Glico 解説 (「巡回行列の積は巡回行列」を使ってO(N^2logK)にするテク)
- AGC013 Placing Squares 解説1 解説2
- CSA69 The Wall 解説1 解説2
- yukicoder No.659 徘徊迷路 解説
- AC タイル張り 解説
分割統治
- CF438 Yet Another Minimization Problem 解説
- CF351 Levels and Regions 解説
- CF190 Ciel and Gondolas 解説1 解説2
CHT
- AC スペースエクスプローラー高橋君 解説 （DP高速化ではないがCHTが何かを知るのに最適）
- EDPC Frog 3 解説
- HR Sword profit （これもDP高速化ではない）
- yukicoder No.703 ゴミ拾い Easy 解説
- Codeforces #189 Div1. C Kalila and Dimna in the Logging Industry
- yukicoder No.409 ダイエット
- HackerRank Week of Code 30 Poles
- HR Pair Sums （CHTmax＋分割統治でDPじゃない）
- CF463 Escape Through Leaf （動的CHT+マージテク）
- CF464 Maximize! 解説（CHTmax）
- CSA70 Squared Ends 解説（動的CHT）
- 以下まとめ
http://codeforces.com/blog/entry/8219
http://arc070.contest.atcoder.jp/tasks/arc070_c
http://pekempey.hatenablog.com/archive/category/Convex%20Hull%20Trick
MongeDP
- AtCoder 最適二分探索木
- AtCoder 刺身 解説1 解説2 (AtCoderの最適二分探索木と全く同じ問題)
- SPOJ BRKSTRNG (AtCoderの最適二分探索木と全く同じ問題)
- AtCoder Optimal Tournament 解説1 解説2
- らしい問題
インラインDP
- CF523 Multiplicity 解説
- ARC085 NRE
- ARC073 Many Moves 解説
- 他の類題
- CSA65 Count Arrays 解説
- AC だんだん強く 解説
- AGC009 Division into Two
- EDPC Flowers 解説
きたまさ法
- AC フィボナッチ
- yukicoder No.214 素数サイコロと合成数サイコロ (3-Medium)
- ABC009 漸化式
- CC Random Number Generator （高速きたまさ法のverify問題）
（あんまり関係ないけど）遷移が限られる関係で最適化できる動的計画法問題
