四边形不等式/决策单调性优化

What · 是什么

四边形不等式优化利用「决策单调性」：对形如 f(i)=min_{j≤i} {w(j,i)} 的最优化问题，若成本 w 满足四边形不等式 w(a,c)+w(b,d) ≤ w(a,d)+w(b,c)（a≤b≤c≤d，即「交叉小于包含」），则最优决策点 opt(i) 单调不减。利用这一单调性，可用分治优化（O(n log n)）、二分队列（单调队列记录决策点覆盖区间，O(n log n)）、Knuth 优化（区间 DP，O(n²)）将朴素 O(n²)/O(n³) 大幅降低。经典应用：石子合并最小代价、最优二叉搜索树（Knuth）、IOI2000 邮局、POI2011 Lightning Conductor。

Why · 为什么

How · 实现

伪代码

# 判断 w 是否满足四边形不等式（随机抽样验证 + 理论证明）
for a<=b<=c<=d: assert w(a,c)+w(b,d) <= w(a,d)+w(b,c)

# 分治优化（决策单调）
solve(l, r, optL, optR):
  if l > r: return
  mid = (l+r)//2
  best_j = argmin_{j in [optL, min(mid-1,optR)]} w(j, mid)   # 枚举
  f[mid] = w(best_j, mid)
  solve(l, mid-1, optL, best_j)
  solve(mid+1, r, best_j, optR)

# Knuth 优化（区间DP）
for len in 1..n:
  for i, j=i+len:
    for k in [opt[i][j-1], opt[i+1][j]]:   # 决策界缩到 O(1) 摊还
      f[i][j] = min(f[i][k]+f[k+1][j]) + w(i,j)
    opt[i][j] = 最优 k

Python 实现

def quadrangle_divide_conquer(n, w):
    """分治优化：f[i] = min_{j<i} w(j,i)，要求决策单调。
    w(i,j) 由 callable 提供（这里用 precomputed 2D 列表模拟）。
    返回每个 i 的最优决策与 f[i]。"""
    f = [float('inf')] * (n + 1)
    opt = [0] * (n + 1)
    f[0] = 0

    def solve(l, r, optL, optR):
        if l > r:
            return
        mid = (l + r) // 2
        best_j, best_v = optL, float('inf')
        for j in range(optL, min(mid, optR) + 1):
            v = w(j, mid)
            if v < best_v:
                best_v, best_j = v, j
        opt[mid] = best_j
        f[mid] = best_v
        solve(l, mid - 1, optL, best_j)
        solve(mid + 1, r, best_j, optR)

    solve(1, n, 0, n)
    return f, opt


def knuth_optimization(n, w):
    """Knuth 优化区间 DP：f[i][j] = min_k { f[i][k]+f[k+1][j] } + w(i,j)。
    经典为石子合并/最优BST；此处用通用 cost w(i,j) 实现，O(n^2)。
    """
    f = [[0] * (n + 1) for _ in range(n + 1)]
    opt = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        opt[i][i] = i
    for length in range(2, n + 1):
        for i in range(1, n - length + 2):
            j = i + length - 1
            best_v = float('inf')
            best_k = opt[i][j - 1]
            for k in range(opt[i][j - 1], min(opt[i + 1][j], j - 1) + 1):
                v = f[i][k] + f[k + 1][j] + w(i, j)
                if v < best_v:
                    best_v, best_k = v, k
            f[i][j] = best_v
            opt[i][j] = best_k
    return f[1][n]


def knuth_naive(n, w):
    """朴素区间 DP O(n^3) 对拍"""
    f = [[0] * (n + 1) for _ in range(n + 1)]
    for length in range(2, n + 1):
        for i in range(1, n - length + 2):
            j = i + length - 1
            f[i][j] = min(f[i][k] + f[k + 1][j] for k in range(i, j)) + w(i, j)
    return f[1][n]


def cost_for_prefix_squares(n):
    """邮局/分治DP 的经典 w：sum |pos[k] - pos[j]|，满足四边形不等式。
    此处构造简单的递推以做自测（w(j,i) = 任意满足单调性的函数）。"""
    import random
    random.seed(3)
    pos = sorted(random.sample(range(1, 10000), n))
    pref = [0] * (n + 1)
    for i in range(n):
        pref[i + 1] = pref[i] + pos[i]
    def w(j, i):
        # w(j,i) = sum_{k=j+1..i} (i-k)*a[k] 型成本，满足四边形不等式
        # 简化用二次型：w(j,i) = (i-j) * (suffix_cost)，保证非负且 Monge
        if j >= i:
            return float('inf')
        # 用「中位数绝对距离」的另一种非负构造：
        # w(j,i) = sum_{t=j+1}^{i} (t-j-1)^2  （恒非负、四边形不等式满足）
        return (i - j - 1) * (i - j) * (i - j + 1) // 3
    return w


def stone_merge_cost(n):
    """石子合并：w(i,j)=sum(a[i..j])，Knuth 优化适用（w 满足四边形不等式）"""
    import random
    random.seed(8)
    a = [random.randint(1, 100) for _ in range(n)]
    pref = [0] * (n + 1)
    for i in range(n):
        pref[i + 1] = pref[i] + a[i]
    def w(i, j):
        return pref[j] - pref[i - 1]
    return w


if __name__ == "__main__":
    import random
    random.seed(41)
    # 分治优化（决策单调）正确性：w 取「到中位数距离」型（Monge）
    for n in [3, 7, 12]:
        w = cost_for_prefix_squares(n)
        f, opt = quadrangle_divide_conquer(n, w)
        # 验证决策单调
        assert all(opt[i] <= opt[i + 1] for i in range(1, n))
        # 与朴素逐点比对
        for i in range(1, n + 1):
            exp = min(w(j, i) for j in range(0, i))
            assert abs(f[i] - exp) < 1e-9, (i, f[i], exp)
    # Knuth 优化（石子合并）
    for n in [3, 6, 10]:
        w = stone_merge_cost(n)
        got = knuth_optimization(n, w)
        exp = knuth_naive(n, w)
        assert got == exp, (n, got, exp)
    # 决策单调性 + 四边形不等式抽样验证
    w = cost_for_prefix_squares(30)
    ok = True
    for a in range(0, 10):
        for b in range(a, 10):
            for c in range(b, 10):
                for dd in range(c, 10):
                    if w(a, c) + w(b, dd) > w(a, dd) + w(b, c) + 1e-9:
                        ok = False
    assert ok, "quadrangle inequality violated"
    print("All tests passed.")

易错点

• 未验证 w 满足四边形不等式就套优化，答案错误无提示
• 分治边界：决策枚举上界误用 mid-1（应为 min(mid, optR)）
• Knuth 优化中 opt[i][j-1] ≤ k ≤ opt[i+1][j] 的边界初始化错误
• 取最大/最小最优决策不一致导致决策区间不连续

例题

信源

• OI Wiki✓ https://oi-wiki.org/dp/opt/quadrangle/
• CP-Algorithms✓ https://cp-algorithms.com/dynamic_programming/knuth-optimization.html
• 论文✓ F. F. Yao, Efficiency of dynamic programming, JACM 1982