四边形不等式的数学定义与核心性质

在算法设计与优化中，四边形不等式是证明动态规划决策单调性的重要数学工具。对于定义在整数域上的二维函数 \(W(i, j)\)，若对于任意满足 \(a \leq b \leq c \leq d\) 的整数，均成立以下不等式：

\[ W(a, d) + W(b, c) \geq W(a, c) + W(b, d) \]

则称函数 \(W\) 满足四边形不等式。

核心性质与证明

在实际应用中，直接验证上述定义往往较为繁琐。我们可以通过一个更弱的局部条件来推导全局性质：若对于任意相邻的整数 \(i < j\)，满足：

\[ W(i, j+1) + W(i+1, j) \geq W(i, j) + W(i+1, j+1) \quad \text{①} \]

那么 \(W\) 必然满足四边形不等式。

证明过程：

首先，固定 \(j\)，对 \(i\) 进行累加。取 \(i+1 < i+2 \leq j < j+1\)，令 \(i' = i+1\)，代入条件 ① 可得：

\[ W(i+1, j+1) + W(i+2, j) \geq W(i+1, j) + W(i+2, j+1) \quad \text{②} \]

将 ① 与 ② 相加，消去中间项 \(W(i+1, j+1)\) 和 \(W(i+1, j)\)，整理后得到：

\[ W(i, j+1) + W(i+2, j) \geq W(i, j) + W(i+2, j+1) \]

通过数学归纳法不断累加，可推广至任意 \(a \leq b\)，即：

\[ W(a, j+1) + W(b, j) \geq W(a, j) + W(b, j+1) \quad \text{③} \]

接下来，固定 \(a\) 和 \(b\)，对 \(j\) 进行累加。取 \(a \leq b \leq c+1 < c+2\)，由 ③ 可得：

\[ W(a, c+2) + W(b, c+1) \geq W(a, c+1) + W(b, c+2) \quad \text{④} \]

将 ③ 与 ④ 相加并消去中间项，整理得到：

\[ W(a, c+2) + W(b, c) \geq W(a, c) + W(b, c+2) \]

同理，通过归纳法可将右端点推广至任意 \(d \geq c\)，最终证得对于任意 \(a \leq b \leq c \leq d\)，均有 \(W(a, d) + W(b, c) \geq W(a, c) + W(b, d)\)。

该不等式之所以被称为"四边形不等式"，是因为其几何直观可以映射为四边形边长与对角线的关系，如下图所示：

在特定的几何构造中，该式等价于证明 \(AD + BC \geq AC + BD\)。

动态规划中的决策单调性优化

考虑一类常见的一维动态规划模型（1D1D DP），其状态转移方程为：

\[ f(i) = \min_{0 \leq j < i} \{ f(j) + w(j, i) \} \]

此类方程通常出现在区间划分问题中：将 \(n\) 个元素划分为若干连续段，\(w(j, i)\) 表示区间 \((j, i]\) 的代价，目标是求最小总代价。朴素解法的时间复杂度为 \(\mathcal{O}(n^2)\)。

定义 \(p(i)\) 为状态 \(i\) 的最优决策点，即使得 \(f(j) + w(j, i)\) 取最小值的 \(j\)。若代价函数 \(w\) 满足四边形不等式，则可以利用决策单调性将复杂度优化至 \(\mathcal{O}(n \log n)\)。

决策单调性定理

性质 1： 若 \(w\) 满足四边形不等式，则最优决策点 \(p(i)\) 随 \(i\) 单调不减，即 \(p(i) \leq p(i+1)\)。

性质 2： 若存在 \(x < j\)，且对于某个 \(i > j\)，决策 \(j\) 优于决策 \(x\)（即 \(f(j) + w(j, i) \leq f(x) + w(x, i)\)），则对于所有 \(i' > i\)，决策 \(j\) 依然优于 \(x\)。

证明：

由已知条件 \(f(j) + w(j, i) \leq f(x) + w(x, i)\)，且 \(w\) 满足四边形不等式（注意 \(x < j \leq i < i'\)）：

\[ w(x, i') + w(j, i) \geq w(x, i) + w(j, i') \]

移项可得：

\[ w(j, i') - w(j, i) \leq w(x, i') - w(x, i) \]

将此式与已知不等式相加，即可得到 \(f(j) + w(j, i') \leq f(x) + w(x, i')\)，证明完毕。

算法实现：单调队列与二分查找

基于上述性质，每个决策点 \(j\) 能够优化的状态 \(i\) 构成一个连续的右半区间 \([L_j, n]\)。我们可以维护一个单调队列，队列中的每个元素是一个三元组 \((l, r, c)\)，表示在状态区间 \([l, r]\) 内，最优决策点均为 \(c\)。

当计算完 \(f(i)\) 并准备将 \(i\) 作为新决策点加入队列时，我们从队尾开始检查。若 \(i\) 在队尾区间的左端点优于原决策点，则直接弹出队尾；若在右端点优于原决策点，则通过二分查找确定新旧决策点的分界位置，截断原区间并将新三元组入队。此方法可将均摊时间复杂度降至 \(\mathcal{O}(n \log n)\)。此外，该模型也可通过分治法实现同等复杂度的优化。

经典算法实战：玩具装箱问题

以 P3195 [HNOI2008] 玩具装箱为例。设 \(f(i)\) 为前 \(i\) 个玩具的最小费用，\(S(i)\) 为前缀和。转移方程为：

\[ f(i) = \min_{0 \leq j < i} \{ f(j) + (S(i) - S(j) + i - j - 1 - L)^2 \} \]

令 \(X(i) = S(i) + i\)，\(C = L + 1\)，则代价函数 \(w(j, i) = (X(i) - X(j) - C)^2\)。

四边形不等式证明：

设 \(Q = S(i) - S(j) - 1 - L\)，则 \(w(j, i) = Q^2\)。展开交叉项与包含项的差值：

\[ w(j, i) + w(j+1, i+1) - w(j+1, i) - w(j, i+1) = -2(C_{i+1}+1)(C_{j+1}+1) \]

由于玩具长度 \(C \geq 1\)，该差值恒小于等于 \(-8\)，即严格满足 \(w(j, i) + w(j+1, i+1) \leq w(j+1, i) + w(j, i+1)\)，证明其具备决策单调性（本题更常见的解法是将其转化为斜率优化）。

#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    ll L;
    if (!(cin >> n >> L)) return 0;

    vector<ll> prefix(n + 1, 0);
    vector<ll> X(n + 1, 0); 
    vector<ll> Y(n + 1, 0); 
    vector<ll> dp(n + 1, 0);

    for (int i = 1; i <= n; ++i) {
        ll c;
        cin >> c;
        prefix[i] = prefix[i - 1] + c;
        X[i] = prefix[i] + i;
        Y[i] = (X[i] + L + 1) * (X[i] + L + 1);
    }
    Y[0] = (L + 1) * (L + 1);

    vector<int> q(n + 1);
    int head = 0, tail = 0;
    q[tail++] = 0;

    auto slope = [&](int j1, int j2) -> double {
        return (double)(dp[j2] + Y[j2] - dp[j1] - Y[j1]) / (X[j2] - X[j1]);
    };

    for (int i = 1; i <= n; ++i) {
        while (head + 1 < tail && slope(q[head], q[head + 1]) <= 2.0 * X[i]) {
            head++;
        }
        int best_j = q[head];
        dp[i] = dp[best_j] + (X[i] - X[best_j] - L - 1) * (X[i] - X[best_j] - L - 1);

        while (head + 1 < tail && slope(q[tail - 2], q[tail - 1]) >= slope(q[tail - 1], i)) {
            tail--;
        }
        q[tail++] = i;
    }

    cout << dp[n] << "\n";
    return 0;
}

经典算法实战：诗人小G问题

P1912 [NOI2009] 诗人小G 的状态转移方程为：

\[ f(i) = \min_{0 \leq j < i} \{ f(j) + |S(i) - S(j) + i - j - 1 - L|^P \} \]

为证明其决策单调性，需验证 \(G_j(i) = |S(i) + i - (S(j) + j) - (1 + L)|^P\) 满足四边形不等式。通过变量代换，问题等价于证明函数 \(h(x) = |x|^P - |x+z|^P\) （其中 \(z \geq 0\)）在定义域内单调递减。

通过分类讨论 \(x\) 的正负及 \(P\) 的奇偶性，对 \(h(x)\) 求导可得 \(h'(x) \leq 0\) 恒成立，从而严格证明了其满足四边形不等式。因此，可直接应用单调队列结合二分查找的 \(\mathcal{O}(n \log n)\) 算法。

#include <iostream>
#include <vector>
#include <string>
#include <cmath>

using namespace std;
using ld = long double;

struct Segment {
    int opt, left, right;
};

int n, L, P;
vector<int> len_sum;
vector<ld> dp;
vector<int> opt_from;
vector<Segment> q;
int head, tail;

ld calc_cost(int j, int i) {
    ld base = abs(len_sum[i] - len_sum[j] + i - j - 1 - L);
    ld res = 1.0;
    for (int k = 0; k < P; ++k) res *= base;
    return dp[j] + res;
}

void add_decision(int i) {
    int pos = n + 1;
    while (head <= tail && calc_cost(q[tail].opt, q[tail].left) >= calc_cost(i, q[tail].left)) {
        pos = q[tail--].left;
    }
    if (head <= tail && calc_cost(q[tail].opt, q[tail].right) >= calc_cost(i, q[tail].right)) {
        int l = q[tail].left, r = q[tail].right;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (calc_cost(q[tail].opt, mid) >= calc_cost(i, mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        q[tail].right = r - 1;
        pos = r;
    }
    if (pos <= n) {
        q[++tail] = {i, pos, n};
    }
}

void solve() {
    cin >> n >> L >> P;
    vector<string> words(n + 1);
    len_sum.assign(n + 1, 0);
    dp.assign(n + 1, 0);
    opt_from.assign(n + 1, 0);
    q.assign(n + 2, {0, 0, 0});
    
    for (int i = n; i >= 1; --i) {
        cin >> words[i];
    }
    for (int i = 1; i <= n; ++i) {
        len_sum[i] = len_sum[i - 1] + words[i].length();
    }

    head = 0; tail = 0;
    q[0] = {0, 1, n};

    for (int i = 1; i <= n; ++i) {
        dp[i] = calc_cost(q[head].opt, i);
        opt_from[i] = q[head].opt;
        if (q[head].right == i) head++;
        q[head].left = i + 1;
        add_decision(i);
    }

    if (dp[n] > 1e18) {
        cout << "Too hard to arrange\n";
    } else {
        cout << (long long)dp[n] << "\n";
        for (int i = n; i > 0; i = opt_from[i]) {
            for (int j = i; j > opt_from[i]; --j) {
                cout << words[j];
                if (j != opt_from[i] + 1) cout << " ";
            }
            cout << "\n";
        }
    }
    cout << "--------------------\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    if (cin >> T) {
        while (T--) solve();
    }
    return 0;
}