Divide And Conquer Optimization (dp/divide-and-conquer-optimization.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2026-08-23 09:13:28+00:00
• Include: #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

vector<vector<T> > divide_and_conquer_optimization( int H, int W, T INF, const function<T(int, int)>& f, const Compare& comp = Compare())

dp 配列を返す。

計算量

• $O(HW \log W)$

Depends on

• Monotone Minima (dp/monotone-minima.hpp)

Verified with

• test/verify/aoj-2603.test.cpp

Code

#pragma once

#include <functional>
#include <vector>

#include "monotone-minima.hpp"

template <typename T, typename Compare = std::less<T> >
std::vector<std::vector<T> > divide_and_conquer_optimization(
    int H, int W, T INF, const std::function<T(int, int)>& f,
    const Compare& comp = Compare()) {
  std::vector<std::vector<T> > dp(H + 1, std::vector<T>(W + 1, INF));
  dp[0][0] = 0;
  for (int i = 1; i <= H; i++) {
    std::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, [&](int j, int old_k, int new_k) {
      return comp(get_cost(j, new_k), get_cost(j, old_k));
    });
    for (int j = 0; j <= W; j++) dp[i][j] = get_cost(j, ret[j]);
  }
  return dp;
}

#line 2 "dp/divide-and-conquer-optimization.hpp"

#include <functional>
#include <vector>

#line 2 "dp/monotone-minima.hpp"

#line 4 "dp/monotone-minima.hpp"

template <typename Select>
std::vector<int> monotone_minima_select(int H, int W, Select select) {
  std::vector<int> ret(H, -1);
  if (H == 0 || W == 0) return ret;
  auto dfs = [&](auto&& self, int top, int bottom, int left,
                 int right) -> void {
    if (top > bottom) return;
    int line = (top + bottom) / 2;
    int best = select(line, left, right + 1);
    ret[line] = best;
    self(self, top, line - 1, left, best);
    self(self, line + 1, bottom, best, right);
  };
  dfs(dfs, 0, H - 1, 0, W - 1);
  return ret;
}

template <typename F>
std::vector<int> monotone_minima(int H, int W, F comp) {
  return monotone_minima_select(H, W, [&](int row, int left, int right) {
    int best = left;
    for (int column = left + 1; column < right; ++column) {
      if (comp(row, best, column)) best = column;
    }
    return best;
  });
}
#line 7 "dp/divide-and-conquer-optimization.hpp"

template <typename T, typename Compare = std::less<T> >
std::vector<std::vector<T> > divide_and_conquer_optimization(
    int H, int W, T INF, const std::function<T(int, int)>& f,
    const Compare& comp = Compare()) {
  std::vector<std::vector<T> > dp(H + 1, std::vector<T>(W + 1, INF));
  dp[0][0] = 0;
  for (int i = 1; i <= H; i++) {
    std::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, [&](int j, int old_k, int new_k) {
      return comp(get_cost(j, new_k), get_cost(j, old_k));
    });
    for (int j = 0; j <= W; j++) dp[i][j] = get_cost(j, ret[j]);
  }
  return dp;
}

Back to top page