#include "dp/monge-d-edge-shortest-path-enumerate.hpp"
#pragma once #include <functional> #include <vector> using namespace std; #include "monotone-minima.hpp" // 辺コストが monge である DAG の D 辺 0-N 最短路 vector<long long> enumerate_monge_d_edge_shortest_path( int N, const function<long long(int, int)>& f, long long unreached = (1LL << 62) - 1) { using T = __int128_t; T INF = (T{1} << (sizeof(T) * 8 - 2)) - 1; vector<long long> ans(N + 1, unreached); vector<T> dp(N + 1, INF); dp[0] = 0; for (int d = 1; d <= N; d++) { vector<int> midx = monotone_minima<T>(N + 1, N + 1, [&](int j, int i) -> T { return i < j ? dp[i] + f(i, j) : INF; }); for (int i = N; i >= d; i--) dp[i] = dp[midx[i]] + f(midx[i], i); ans[d] = dp[N]; } return ans; } /** * @brief monge グラフ上の d-辺最短路の d=1,...,N における列挙 */
#line 2 "dp/monge-d-edge-shortest-path-enumerate.hpp" #include <functional> #include <vector> using namespace std; #line 2 "dp/monotone-minima.hpp" #line 5 "dp/monotone-minima.hpp" using namespace std; // NxN 行列がある // m_i := argmin_j (A_{i,j}) が単調増加であるときに m_i を列挙する // f(i, j, k) : // A[i][j] と A[i][k] を比較 (j < k が保証されている) // A[i][j] <= A[i][k] のとき true を返す関数を入れる (等号はどちらでもよい) vector<int> monotone_minima(int N, int M, const function<bool(int, int, int)>& f) { vector<int> res(N); auto dfs = [&](auto rc, int is, int ie, int l, int r) -> void { if (is == ie) return; int i = (is + ie) / 2; int m = l; for (int k = l + 1; k < r; k++) { if (!f(i, m, k)) m = k; } res[i] = m; rc(rc, is, i, l, m + 1); rc(rc, i + 1, ie, m, r); }; dfs(dfs, 0, N, 0, M); return res; } // NxM 行列がある // m_i := argmin_j (A_{i,j}) が単調増加であるときに m_i を列挙する // A(i, j) : A[i][j] を返す関数 template <typename T> vector<int> monotone_minima(int N, int M, const function<T(int, int)>& A) { function<bool(int, int, int)> f = [&](int i, int j, int k) -> bool { return A(i, j) <= A(i, k); }; return monotone_minima(N, M, f); } /** * @brief monotone minima */ #line 8 "dp/monge-d-edge-shortest-path-enumerate.hpp" // 辺コストが monge である DAG の D 辺 0-N 最短路 vector<long long> enumerate_monge_d_edge_shortest_path( int N, const function<long long(int, int)>& f, long long unreached = (1LL << 62) - 1) { using T = __int128_t; T INF = (T{1} << (sizeof(T) * 8 - 2)) - 1; vector<long long> ans(N + 1, unreached); vector<T> dp(N + 1, INF); dp[0] = 0; for (int d = 1; d <= N; d++) { vector<int> midx = monotone_minima<T>(N + 1, N + 1, [&](int j, int i) -> T { return i < j ? dp[i] + f(i, j) : INF; }); for (int i = N; i >= d; i--) dp[i] = dp[midx[i]] + f(midx[i], i); ans[d] = dp[N]; } return ans; } /** * @brief monge グラフ上の d-辺最短路の d=1,...,N における列挙 */