This documentation is automatically generated by online-judge-tools/verification-helper
#include "dp/divide-and-conquer-optimization.hpp"
$dp[i][j] = \min_{0 \leq k \lt j}\{dp[i-1][k]+f(k,j)\}$ の形のDPを高速化するテク.
$f(k,j)$ は $0 \leq k \lt j \leq W$ で定義される $2$ 変数関数.
各行について Monotone-Minima を適用する.
divide_and_conquer_optimization(H, W, INF, f)
: dp 配列を返す.#include "monotone-minima.hpp"
template <typename T, typename Compare = less<T> >
vector<vector<T> > divide_and_conquer_optimization(
int H, int W, T INF, const function<T(int, int)> &f,
const Compare &comp = Compare()) {
vector<vector<T> > dp(H + 1, vector<T>(W + 1, INF));
dp[0][0] = 0;
for (int i = 1; i <= H; i++) {
function<T(int, int)> get_cost = [&](int y, int x) {
if (x >= y) return INF;
return dp[i - 1][x] + f(x, y);
};
auto ret = monotone_minima(W + 1, W + 1, get_cost, comp);
for (int j = 0; j <= W; j++) dp[i][j] = ret[j].second;
}
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;
}
#line 2 "dp/divide-and-conquer-optimization.hpp"
template <typename T, typename Compare = less<T> >
vector<vector<T> > divide_and_conquer_optimization(
int H, int W, T INF, const function<T(int, int)> &f,
const Compare &comp = Compare()) {
vector<vector<T> > dp(H + 1, vector<T>(W + 1, INF));
dp[0][0] = 0;
for (int i = 1; i <= H; i++) {
function<T(int, int)> get_cost = [&](int y, int x) {
if (x >= y) return INF;
return dp[i - 1][x] + f(x, y);
};
auto ret = monotone_minima(W + 1, W + 1, get_cost, comp);
for (int j = 0; j <= W; j++) dp[i][j] = ret[j].second;
}
return dp;
}