四边形不等式优化

概述

四边形不等式优化利用 决策单调性（ $opt (i_{1}) \leq opt (i_{2})$ 当 $i_{1} < i_{2}$ ），将 DP 复杂度从 $O (n^{2})$ 降至 $O (n lo g n)$ 或 $O (n^{2})$ 。核心条件是成本函数 $w (j, i)$ 满足四边形不等式：

w (a, c) + w (b, d) \leq w (a, d) + w (b, c), a \leq b \leq c \leq d

分治优化（1D1D）

适用 $f_{i} = min_{j < i} w (j, i)$ ，且 $w$ 可 $O (1)$ 或移动访问。每次计算中点决策后递归左右两边。

void solve(int l, int r, int optL, int optR) {
    int mid = (l + r) / 2, optM = optL;
    for (int j = optL; j <= min(mid - 1, optR); ++j)
        if (w(j, mid) < w(optM, mid)) optM = j;
    f[mid] = w(optM, mid);
    if (l < mid) solve(l, mid - 1, optL, optM);
    if (mid < r) solve(mid + 1, r, optM, optR);
}

Knuth 优化（区间 DP）

适用于 $f_{j, i} = min_{k \in [j, i - 1]} {f_{j, k} + f_{k + 1, i} + w (j, i)}$ ，且 $w$ 满足四边形不等式与区间包含单调性。此时决策点满足 $opt (j, i - 1) \leq opt (j, i) \leq opt (j + 1, i)$ ，可将复杂度从 $O (n^{3})$ 降至 $O (n^{2})$ 。

问题模板

题目	题号	说明
邮局	P4767	区间分拆 + 四边形不等式 / WQS 二分
诗人小G	P1912	1D1D 决策单调性 + 二分队列
Lightning Conductor	POI2011	分治优化， $w (j, i) = - i - j$
守卫	Codeforces 321E	分治优化

四边形不等式定义

对于成本函数 $w (j, i)$ （ $j \leq i$ ），若对任意 $a \leq b \leq c \leq d$ 有：

w (a, c) + w (b, d) \leq w (a, d) + w (b, c)

则称 $w$ 满足四边形不等式（quadrangle inequality）。直观理解为 交叉和 ≤ 包含和。

区间包含单调性： 若对任意 $j \leq i$ 有 $w (j, i + 1) \geq w (j, i)$ ，则称 $w$ 满足区间包含单调性（单调递增）。

两个性质同时满足时，大多数 DP 都具备决策单调性。

决策单调性证明

考虑 $f_{i} = min_{j < i} {w (j, i)}$ ，记 $opt (i)$ 为 $f_{i}$ 的最优决策点。

定理： 若 $w$ 满足四边形不等式，则 $opt (i)$ 关于 $i$ 单调不减（ $i_{1} < i_{2} \Rightarrow opt (i_{1}) \leq opt (i_{2})$ ）。

证明思路： 设 $i_{1} < i_{2}$ ， $p = opt (i_{1})$ ， $q = opt (i_{2})$ ，欲证 $p \leq q$ 。

反证：若 $q < p$ ，由四边形不等式：

w (q, i_{1}) + w (p, i_{2}) \leq w (q, i_{2}) + w (p, i_{1})

由 $p$ 对 $i_{1}$ 最优知 $w (p, i_{1}) \leq w (q, i_{1})$ ，代入得 $w (p, i_{2}) \leq w (q, i_{2})$ ，与 $q$ 对 $i_{2}$ 最优矛盾（除非相等，此时也可取 $p$ ）。故 $p \leq q$ 。

Knuth 优化

适用条件： 区间 DP $f_{j, i} = min_{k \in [j, i - 1]} {f_{j, k} + f_{k + 1, i} + w (j, i)}$ ，且 $w$ 满足四边形不等式和区间包含单调性。

关键性质： 最优决策点满足四边形单调性：

opt (j, i - 1) \leq opt (j, i) \leq opt (j + 1, i)

优化方法： 枚举 $k$ 时只需在 $[opt (j, i - 1), opt (j + 1, i)]$ 内搜索。总枚举量 $O (n^{2})$ 。

for (int len = 2; len <= n; ++len) {
    for (int j = 1; j + len - 1 <= n; ++j) {
        int i = j + len - 1;
        f[j][i] = INF;
        for (int k = opt[j][i-1]; k <= opt[j+1][i]; ++k) {
            if (f[j][k] + f[k+1][i] + w(j,i) < f[j][i]) {
                f[j][i] = f[j][k] + f[k+1][i] + w(j,i);
                opt[j][i] = k;
            }
        }
    }
}

复杂度： 朴素 $O (n^{3})$ ，Knuth 优化 $O (n^{2})$ ，常数较小。常见于石子合并、最优二叉树等。

分治 DP 优化（Divide & Conquer DP）

适用问题： 分层 DP $f_{k, i} = min_{j < i} {f_{k - 1, j} + w (j + 1, i)}$ ，外层 $k$ 层，内层 $i$ 个状态， $w$ 满足四边形不等式。

核心思想： 对每层 $k$ ，计算 $f_{k, 1.. n}$ 时利用决策单调性分治，避免枚举所有 $j$ 。

void solve(int k, int l, int r, int optL, int optR) {
    if (l > r) return;
    int mid = (l + r) / 2, best = optL;
    f[k][mid] = INF;
    for (int j = optL; j <= min(mid - 1, optR); ++j) {
        ll val = f[k-1][j] + w(j + 1, mid);
        if (val < f[k][mid]) {
            f[k][mid] = val;
            best = j;
        }
    }
    solve(k, l, mid - 1, optL, best);
    solve(k, mid + 1, r, best, optR);
}
 
for (int k = 1; k <= K; ++k) solve(k, 1, n, 0, n - 1);

复杂度： 每层递归中， $j$ 的总枚举次数为 $O (n lo g n)$ ， $K$ 层总复杂度 $O (K n lo g n)$ 。

对比：

方法	复杂度	适用场景
朴素	$O (K n^{2})$	无限制
分治优化	$O (K n lo g n)$	决策单调， $w$ 难 $O (1)$ 但可移动
二分队列	$O (K n lo g n)$	决策单调， $w$ 可 $O (1)$ 计算
Knuth	$O (n^{2})$	区间 DP，四边形不等式

完整示例：P4767 邮局

题意： $n$ 个村庄在数轴上，选 $K$ 个位置建邮局，求所有村庄到最近邮局距离和的最小值。

状态： $f_{k, i}$ 表示前 $i$ 个村庄建 $k$ 个邮局的最小距离和。

转移： $f_{k, i} = min_{j < i} {f_{k - 1, j} + w (j + 1, i)}$ 。

成本函数： $w (l, r)$ 表示在 $[l, r]$ 区间建一个邮局的最小距离和。邮局建在中位数村庄处最优。

w (l, r) = t = l \sum r ∣ a_{t} - a_{mi d} ∣, mi d = ⌊(l + r) /2 ⌋

预处理前缀和实现 $O (1)$ 查询：

int w(int l, int r) {
    int m = (l + r) / 2;
    int lenL = m - l, lenR = r - m;
    return a[m] * lenL - (s[m-1] - s[l-1]) + (s[r] - s[m]) - a[m] * lenR;
}

$w$ 满足四边形不等式，可用分治优化。复杂度 $O (K n lo g n)$ ，足以通过 $n \leq 3000$ 的数据。

决策单调性检验方法

实际竞赛中不一定要严格证明四边形不等式，可使用打表法验证：

运行朴素 $O (n^{2})$ DP 在小数据上
记录 $opt (i)$ 的值
检查 $opt (i)$ 是否单调不减

若通过，则大概率满足决策单调性，可直接应用分治/二分队列优化。

多平台练习

RootStack

探索