本节介绍DP的优化方法之一————四边形不等式。

        在列状态转移方程时，常常会遇到如下形式的方程：

        这种方程很常见，比如题目合并石子的方程就满足这种形式。m为转移的代价。dp时间复杂度为O(n2)，转移枚举为O(n)，故总体时间复杂度为O(n3)。可以用四边形不等式将其减至O(n2)复杂度。
        如果对于a≤i<j≤b，总有：

        则称m满足四边形不等式，一句话概括为：交叉小于包含。下面介绍三个重要定理。

【定理一】m满足四边形不等式的充要条件是 $m(i,j)+m(i+1,j+1)≤m(i+1,j)+m(i,j+1),i<j$。

证明：
        显然这个不等式是m满足四边形不等式的特殊情形，于是必要性成立，下证充分性。只需证明$m(i,j)+m(i+a,j+b)≤m(i+a,j)+m(i,j+b),i\leq i+a < j \leq j+b$，这里只对i的情况进行讨论，采用数学归纳法。
        由已知可知，$m(i,j)+m(i+1,j+1)\leq m(i+1,j)+m(i,j+1)$是成立的。假设$m(i,j)+m(i+k,j+1)\leq m(i+k,j)+m(i,j+1)$成立，那么由已知，应有：

        与假设的式子联立，立即得到：

        也就是：

        由归纳法便知$m(i,j)+m(i+a,j+1)≤m(i+a,j)+m(i,j+1)$是成立的，j类似证明即可。两个结合便可证明四边形不等式，于是定理一得证。这个定义可以帮助判断m是否满足四边形不等式。

【定理二】若m满足四边形不等式，则dp也满足四边形不等式。

证明：
        只需证明$dp(a,j)+dp(i,b)\leq dp(i,j)+dp(a,b),a\leq i < j\leq b$。采用数学归纳法。
        a=i<i+1=j=b时显然成立。对于固定的a、i，假设在a≤i<j≤b≤P时成立，那么在b=P+1时：
        假设dp(i,j)在k=x处取得最优解，dp(a,P+1)在k=y处取到最优解，假设x≤y(x >y时类似可证)，那么上式等价于：

        注意到：

        而m满足四边形不等式，也就是有：

        由于a≤i<x≤y<P+1由归纳假设，有(i=x时也成立)：

        于是有：

        那么：

        也就是对P+1也成立，由归纳法可知dp也满足四边形不等式。这个定理是定理三的基础。

【定理三】若dp满足四边形不等式，设S(i,j)为dp(i,j)取最优解的k值，那么有$S(i,j-1)\leq S(i,j)\leq S(i+1,j)$

证明：
        设$dp_k(i,j)=dp(i,k)+dp(k+1,j)+m(i,j)，S(i,j)=d$那么：
$(dp_k(i+1,j)-dp_d(i+1,j))-(dp_k(i,j)-dp_d(i,j))$
$=(dp_k(i+1,j)+dp_d(i,j))-(dp_d(i+1,j)+dp_k(i,j))$
$=(dp(i+1,k)+dp(k,j)+dp(i,d)+dp(d,j)+m(i+1,j)+m(i,j))-\\
(dp(i+1,d)+dp(d,j)+dp(i,k)+dp(k,j)+m(i+1,j)+m(i,j))$
$=(dp(i+1,k)+dp(i,d))-(dp(i+1,d)+dp(i,k))$

        倘若k<d，那么有i<i+1<k<d。由dp的四边形不等式，有：

        于是$(dp_k(i+1,j)-dp_d(i+1,j))-(dp_k(i,j)-dp_d(i,j))\geq 0$，即：

        由于S(i,j)=d，故$dp_k(i,j)\geq dp_d(i,j)$，所以：

        这个式子说明，k<d时不能取到比k=d更优的解，所以S(i+1,j)≥d。S(i,j-1)≤d同理可证，定理三成立。

        定理三表明，k的取值可以优化到一个很小的范围内，即[S(i,j-1),S(i+1,j)]，开一个数组S储存这个结果，时间复杂度便压缩到O(n2)。

        但是对于最大值又如何做呢？最大值不能用四边形不等式，但是它有另一个性质：最大值的k值一定在端点处取到。这个性质仍然可以帮助优化算法。容易验证石子合并的m是满足四边形不等式的，于是可以用四边形不等式优化DP过程，下面给出优化版代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>

#define N 100*2+1
using namespace std;
int n, op[N], sum[N] = {0};
int dp1[N][N], dp2[N][N], S[N][N];
int ans1 = 0x7fffffff, ans2 = -1;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> op[i];
        op[i + n] = op[i];
    }
    for (int i = 1; i <= 2 * n; i++)sum[i] = op[i] + sum[i - 1];//前缀和
    for (int j = 2 * n; j >= 1; j--) {//最大值
        for (int z = j; z <= 2 * n; z++) {
            if (j == z)dp2[j][z] = 0;
            else dp2[j][z] = max(dp2[j + 1][z], dp2[j][z - 1]) + sum[z] - sum[j - 1];
        }
    }
    for (int j = 2 * n; j >= 1; j--) {//最小值
        for (int z = j; z <= 2 * n; z++) {
            if (j == z)S[j][z] = j, dp1[j][z] = 0;
            else {
                dp1[j][z] = 0x7fffffff;
                for (int k = S[j][z - 1]; k <= S[j + 1][z] && k < z; k++) {
                    if (dp1[j][k] + dp1[k + 1][z] + sum[z] - sum[j - 1] < dp1[j][z])
                        dp1[j][z] = dp1[j][k] + dp1[k + 1][z] + sum[z] - sum[j - 1], S[j][z] = k;
                }
            }
        }
    }
    for (int i = 1; i <= n; i++)ans1 = min(ans1, dp1[i][i + n - 1]), ans2 = max(ans2, dp2[i][i + n - 1]);
    cout << ans1 << endl << ans2;
    return 0;
}

        对于环的处理，仍然是剪环为链，但是这里的做法比原先的做法高明的多（直接将n个石子扩展为2n个，再寻找答案），于是时间复杂度降了一维。再用四边形不等式降一维，总体时间复杂度便为O(n2)。