monotone_minima_value

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

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

概要

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

パラメータ

戻り値

各行の最適値

計算量

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

関連項目

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