This documentation is automatically generated by online-judge-tools/verification-helper
#include "dp/monotone-minima.hpp"
$2$ 変数関数 $f(i, j) (0 \leq i \lt H, 0 \leq j \lt W)$ が Monotone であるとは, すべての $k$ に対して $\mathrm{argmin} f(k, *) \leq \mathrm{argmin} f(k + 1, *)$ を満たすことをいう. つまり各行の最小値をとる位置が右下に単調に下がっていることを意味する.
Monge $\Rightarrow$ Totally Monotone(TM) $\Rightarrow$ Monotone なので, Monotone は弱い条件である.
monotone_minima(H, W, f, comp)
: 各行について, 最小値をとる位置と最小値をペアで返す. f
は $2$ 変数関数, comp
は比較関数.template <typename T, typename Compare = less<T> >
vector<pair<int, T> > monotone_minima(int H, int W,
const function<T(int, int)> &f,
const Compare &comp = Compare()) {
vector<pair<int, T> > dp(H);
function<void(int, int, int, int)> dfs = [&](int top, int bottom, int left,
int right) {
if (top > bottom) return;
int line = (top + bottom) / 2;
T ma;
int mi = -1;
for (int i = left; i <= right; i++) {
T cst = f(line, i);
if (mi == -1 || comp(cst, ma)) {
ma = cst;
mi = i;
}
}
dp[line] = make_pair(mi, ma);
dfs(top, line - 1, left, mi);
dfs(line + 1, bottom, mi, right);
};
dfs(0, H - 1, 0, W - 1);
return dp;
}
#line 1 "dp/monotone-minima.hpp"
template <typename T, typename Compare = less<T> >
vector<pair<int, T> > monotone_minima(int H, int W,
const function<T(int, int)> &f,
const Compare &comp = Compare()) {
vector<pair<int, T> > dp(H);
function<void(int, int, int, int)> dfs = [&](int top, int bottom, int left,
int right) {
if (top > bottom) return;
int line = (top + bottom) / 2;
T ma;
int mi = -1;
for (int i = left; i <= right; i++) {
T cst = f(line, i);
if (mi == -1 || comp(cst, ma)) {
ma = cst;
mi = i;
}
}
dp[line] = make_pair(mi, ma);
dfs(top, line - 1, left, mi);
dfs(line + 1, bottom, mi, right);
};
dfs(0, H - 1, 0, W - 1);
return dp;
}