convex/monge/monge_dp_update.hpp

• View this file on GitHub
• Last update: 2026-05-31 18:13:57+09:00
• Include: #include "convex/monge/monge_dp_update.hpp"

Depends on

• convex/smawk.hpp

Code

#pragma once
#include "convex/smawk.hpp"

// newdp[j] = min_{0 <= i < j} dp[i] + f(i, j)
template <typename T, typename F>
vc<T> monge_dp_update(int N, vc<T>& dp, F f) {
  assert(len(dp) == N + 1);

  auto select = [&](int i, int j, int k) -> int {
    // row i corresponds to destination i.
    // valid source columns are k < i.
    if (i <= k) return j;
    return (dp[j] + f(j, i) > dp[k] + f(k, i) ? k : j);
  };

  vc<int> I = smawk(N + 1, N + 1, select);

  vc<T> newdp(N + 1, infty<T>);
  FOR(j, N + 1) {
    int i = I[j];
    if (i < j) chmin(newdp[j], dp[i] + f(i, j));
  }
  return newdp;
}

#line 2 "convex/smawk.hpp"

// 各行の最適列を求める.
// better(i,j,k): 行 i において列 k が列 j より良いとき true.
// 適用条件：totally monotone matrix.
// 残念ながら monotone minima より高速な場合が存在しない説がある
// https://codeforces.com/contest/1423/problem/M
template <typename F>
vc<int> smawk(int H, int W, F better) {
  if (H == 0) return {};
  assert(W > 0);

  auto dfs = [&](auto& dfs, vc<int> X, vc<int> Y) -> vc<int> {
    int N = len(X);
    if (N == 0) return {};

    vc<int> YY;
    for (auto&& y : Y) {
      while (len(YY)) {
        int py = YY.back(), x = X[len(YY) - 1];
        if (!better(x, py, y)) break;
        YY.pop_back();
      }
      if (len(YY) < len(X)) YY.eb(y);
    }

    vc<int> XX;
    FOR(i, 1, len(X), 2) XX.eb(X[i]);

    vc<int> II = dfs(dfs, XX, YY);
    vc<int> I(N);
    FOR(i, len(II)) I[i + i + 1] = II[i];

    int p = 0;
    FOR(i, 0, N, 2) {
      int lim = (i + 1 == N ? Y.back() : I[i + 1]);
      int best = Y[p];
      while (Y[p] < lim) {
        ++p;
        if (better(X[i], best, Y[p])) best = Y[p];
      }
      I[i] = best;
    }
    return I;
  };

  vc<int> X(H), Y(W);
  iota(all(X), 0), iota(all(Y), 0);
  return dfs(dfs, X, Y);
}
#line 3 "convex/monge/monge_dp_update.hpp"

// newdp[j] = min_{0 <= i < j} dp[i] + f(i, j)
template <typename T, typename F>
vc<T> monge_dp_update(int N, vc<T>& dp, F f) {
  assert(len(dp) == N + 1);

  auto select = [&](int i, int j, int k) -> int {
    // row i corresponds to destination i.
    // valid source columns are k < i.
    if (i <= k) return j;
    return (dp[j] + f(j, i) > dp[k] + f(k, i) ? k : j);
  };

  vc<int> I = smawk(N + 1, N + 1, select);

  vc<T> newdp(N + 1, infty<T>);
  FOR(j, N + 1) {
    int i = I[j];
    if (i < j) chmin(newdp[j], dp[i] + f(i, j));
  }
  return newdp;
}

Back to top page