説明
$dp[i][j] = \min_{0 \leq k \lt j}\{dp[i-1][k]+f(k,j)\}$
各行について Monotone-Minima
うく
説明を書く
計算量
実装例
依存ライブラリ Monotone-Minima
- divide_and_conquer_optimization($H$, $W$, $INF$, $f$): dp 配列を返す。$f(i, j)$ は区間 $[i, j)$ のコスト。
検証
Codeforces Codeforces Round #438 F - Yet Another Minimization Problem