max_plus_convolution

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

template <class T>
std::vector<T> max_plus_convolution(const std::vector<T> &a, const std::vector<T> &b);

概要

max-plus convolution

パラメータ

計算量

• 出力長を $N$ として $O(N\log N)$

関連項目

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