SMAWK Algorithm
(dp/smawk.hpp)
Description
SMAWK algorithm は,totally monotone 行列の各行の argmin を高速に求めるアルゴリズムである.
単に monotone の場合は monotone minima が使える.
-
vector<int> smawk(int n, int m, F f)
- $A_{i,j}=f(i,j)$ である $n \times m$ 行列 $A$ の各行の argmin を求める
- 時間計算量: $O(n + m)$
Note
多分壊れてる.monotone minima使って
Reference
Code
Back to top page