monotone_minima

関数 · Monotone Minima・min-plus 畳み込み

template <class T, class Comp = std::less<>, class F>
std::vector<int> monotone_minima(int h, int w, F f);

概要

各行の最適列が単調な行列について最適列番号を求める

パラメータ

戻り値

各行の最適列番号

計算量

• $O(h\log w+w\log h)$ 回の要素評価

関連項目

• monotone_minima_value — 各行の最適列が単調な行列について最適値を求める
• min_plus_convolution — min-plus convolution
• max_plus_convolution — max-plus convolution