(cache)DP高速化 - ferinの競プロ帳

dp[i][j] = min_{0<=k<i} {dp[i-1][k] + w(k,j)} の形のDPを高速化するテク
wがQIなら最小値を達成するkに単調性が存在し高速化することができる
Knuth-Yao speedupとこれはargminの単調性を使ってdpテーブルを埋める順を変えてるイメージ

コードを見てもらうのが一番わかりやすいと思うのでコードをのせます。[l,r]の区間ではargminが[optl,optr]の区間に存在するようになっています。dp[i][mid]を区間[optl,optr]を線形に探索することで求めます。するとargminの単調性より[l,mid-1]ではargminが取りうる区間が[optl,optm]、[mid+1,r]ではargminが取りうる区間が[optm,optr]となります。argminが存在しうる範囲が狭まっていくので全てを計算する必要がなく計算量が落ちます。真面目に計算するとO(NKlogN)になるらしい。

function<void(int,int,int,int,int)>
func = [&](int i, int l, int r, int optl, int optr) {
  if(l > r) return;
  int mid = (l+r)/2, optm = -1;
  FOR(j, optl, min(mid+1, optr+1)) {
    if(dp[i][mid] > dp[i-1][j] + W[j+1][mid]) {
      dp[i][mid] = dp[i-1][j] + W[j+1][mid];  // [j+1, mid]
      optm = j;
    }
  }
  func(i, l, mid-1, optl, optm);
  func(i, mid+1, r, optm, optr);
};
// dpの初期値を設定
REP(i, n) dp[0][i] = W[0][i];
FOR(i, 1, n) REP(j, k) dp[i][j] = LLINF;
// DPする
FOR(i, 1, k) func(i, 0, n-1, 0, n-1);
cout << dp[k-1][n-1] << endl;

問題例

Codeforces Round #190 (Div. 1) E. Ciel and Gondolas 解説
 Codeforces Round #438 F. Yet Another Minimization Problem 解説

あとはセグ木を使って高速化とかがありそう
とりあえずDPっぽかったら漸化式を書いて高速化できる形になっていたらQIとかを確認するとかするとよさそう

参考ページ
直前合宿講義スライド