This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ei1333/library
#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)
#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; }