Monge 性 & 単調性を満たす区間 DP の Knuth-Yao Speedup (in O(N^2))
(Optimization/knuth_yao.hpp)

• View this file on GitHub
• Last update: 2026-11-12 11:56:29+09:00
• Include: #include "Optimization/knuth_yao.hpp"

概要

関数 $f$ が Monge であり、かつ区間単調性をもつとき、

dp[i][j] = min_{i <= k < j} (dp[i][k] + dp[k][j]) + f(i, j))

という区間 DP を、$O(N^2)$ の計算量で実行する。

（この区間 DP は、一般的には $O(N^3)$ の計算量を要する形である）

問題例

• KUPC 2012 J - 刺身

参考文献

• tatyam: Monge の手引き書
• 週刊 spaghetti_source: Knuth-Yao speedup

Required by

• Monge 全部乗せ (Optimization/monge_all.hpp)

Code

#pragma once
#include <bits/stdc++.h>
#include <cassert>
using namespace std;

// f: Monge, interval monotone ((N+1) x (N+1))
// dp[i][j] = min_{i <= k < j} (dp[i][k] + dp[k][j]) + f(i, j), in O(N^2)
template<class VAL, class FUNC> VAL KnuthYao(int N, const FUNC &f) {
    VAL INF = numeric_limits<VAL>::max() / 2;
    vector<vector<VAL>> dp(N+1, vector<VAL>(N+1, INF));
    vector<vector<int>> K(N+1, vector<int>(N+1, -1));

    for (int i = 0; i <= N; i++) {
        dp[i][i] = 0, K[i][i] = i;
        if (i < N) dp[i][i+1] = f(i, i+1), K[i][i+1] = i;
    }
    for (int between = 2; between <= N; between++) {
        for (int i = 0; i + between <= N; i++) {
            int j = i + between;
            for (int k = K[i][j-1]; k <= K[i+1][j]; k++) {
                VAL tmp = dp[i][k] + dp[k][j] + f(i, j);
                if (dp[i][j] > tmp) {
                    dp[i][j] = tmp;
                    K[i][j] = k;
                }   
            }
        }
    }
    return dp[0][N];
}

#line 2 "Optimization/knuth_yao.hpp"
#include <bits/stdc++.h>
#line 4 "Optimization/knuth_yao.hpp"
using namespace std;

// f: Monge, interval monotone ((N+1) x (N+1))
// dp[i][j] = min_{i <= k < j} (dp[i][k] + dp[k][j]) + f(i, j), in O(N^2)
template<class VAL, class FUNC> VAL KnuthYao(int N, const FUNC &f) {
    VAL INF = numeric_limits<VAL>::max() / 2;
    vector<vector<VAL>> dp(N+1, vector<VAL>(N+1, INF));
    vector<vector<int>> K(N+1, vector<int>(N+1, -1));

    for (int i = 0; i <= N; i++) {
        dp[i][i] = 0, K[i][i] = i;
        if (i < N) dp[i][i+1] = f(i, i+1), K[i][i+1] = i;
    }
    for (int between = 2; between <= N; between++) {
        for (int i = 0; i + between <= N; i++) {
            int j = i + between;
            for (int k = K[i][j-1]; k <= K[i+1][j]; k++) {
                VAL tmp = dp[i][k] + dp[k][j] + f(i, j);
                if (dp[i][j] > tmp) {
                    dp[i][j] = tmp;
                    K[i][j] = k;
                }   
            }
        }
    }
    return dp[0][N];
}

Back to top page