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

hamayanhamayan's blog

競技プログラミングにおける動的計画法更新最適化まとめ

動的計画法更新最適化?

dp[i][j] = dp[i-1][0] + dp[i-1][1] + ... + dp[i-1][j]
dp[i][j] = min(dp[i-1][0], dp[i-1][1], ..., dp[i-1][j])
dp[i][j] = max(dp[i-1][0], dp[i-1][1], ..., dp[i-1][j])
みたいに区間和や区間最大最小をもたせることで更新を行う。
  • 行列累乗 : DPの更新式を見てみると、一回の更新操作が行列の形になるときがある。この場合は行列を繰り返し二乗法の要領でN乗しておくことで、N番目の要素を高速に取り出せる。
  • Convex Hull Trick : 関数の形式になっている区間最小値を素早く見つける手法 参考1 参考2
  • 分割統治
  • MongeDP
- 別名,Knuth Optimization, Knuth-Yao speedup, 最適二分探索木問題, MongeDP
- 一番短いMongeDPがいいんじゃないかなと思ってる
- 「f(i,l) + f(j,k) >= f(i,k) + f(j,l), i <= j, k <= l」を満たす二変数関数はMonge性を持つ

問題

CFにあったまとめ

セグメントツリーや累積和

行列累乗

CHT

英語を読むのが苦じゃないなら、この問題が入門に最適。
問題概要

高さA[i]の木がN本並んでいる。
チェンソーでそれを切る。
高さは単調増加しており、各木には充電料金が決められている。
チェンソーで1cm切るのに充電を全て使い切る。
充電できるのは切り取られている木から。

「dp[i] = min{j=0...i-1}(dp[j] + A[i] * B[j])」となりCHTで解ける
http://codeforces.com/contest/319/submission/25726136
計算の過程でlonglongを超えてしまうので注意。

「dp[i] = (iの関数) + min{j=0...i-1}((jの関数)*i+(jの関数))」となりCHTで解ける
恐らく、日本語で最も基本的なCHTの入門問題
http://yukicoder.me/submissions/158961

これも比較的一般的な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

(あんまり関係ないけど)遷移が限られる関係で最適化できる動的計画法問題