引入

在dp问题中，我们经常遇见这样的一类问题，他们的dp转移方程是这样的：
$$
f_{l,r} = \min_{k=l}^{r-1}{f_{l,k}+f_{k+1,r}} + w(l,r)\qquad\left(1 \leq l < r \leq n\right)
$$
很显然，这种转移方程，如果不加优化，i,j,k三个变量都需要从1~Nfor一边，时间复杂度$O(n^3)$。

那么，能不能找到一种$O(n^2)$的解决方案呢？

(既然我都问了，当然是能的)

四边形不等式

先给出两个定义：

区间包含单调性

如果对于任意 $l \leq l’ \leq r’ \leq r$，均有 $w(l’,r’) \leq w(l,r)$ 成立，则称函数 $w$ 对于区间包含关系具有单调性。

四边形不等式

如果对于任意 $l_1\leq l_2 \leq r_1 \leq r_2$，均有 $w(l_1,r_1)+w(l_2,r_2) \leq w(l_1,r_2) + w(l_2,r_1)$ 成立，则称函数 $w$ 满足四边形不等式（简记为“交叉小于包含”）。若等号永远成立，则称函数 $w$ 满足 四边形恒等式。

怎么理解呢？
可以理解为一句话，交叉小于包含，即交叉的两个区间，a到c和b到d的值满足小于等于包含的两个区间(bc包含于ad)，
则说这个东西满足四边形不等式，当然这个东西可能是dp数组，也可以是其他数组，比如引入里提到的cost数组，表示的是i到j的花费（比如合并石子问题）

还有两个定理：

定理01

若 $w(l, r)$ 满足区间包含单调性和四边形不等式，则状态 $f_{l,r}$ 满足四边形不等式。（证明略）

定义 $g_{k,l,r}=f_{l,k}+f_{k+1,r}+w(l,r)$ 表示当决策为 $k$ 时的状态值，任取 $l_1\leq l_2\leq r_1\leq r_2$，记 $u=\mathop{\arg\min}\limits_{l_1\leq k < r_2}g_{k,l_1,r_2},v=\mathop{\arg\min}\limits_{l_2\leq k < r_1}g_{k,l_2,r_1}$ 分别表示状态 $f_{l_1,r_2}$ 和 $f_{l_2,r_1}$ 的最小最优决策点。

定理02

若状态 $f$ 满足四边形不等式，记 $m_{l,r}=\min{k:f_{l,r} = g_{k,l,r}}$ 表示最优决策点，则有

$$
m_{l,r-1} \leq m_{l,r} \leq m_{l+1,r} \qquad (l + 1 < r)
$$
证明：
记 $u = m_{l,r},\ k_1=m_{l,r-1},\ k_2=m_{l+1,r}$，分情况讨论：

  1. 若 $k_1>u$，则 $u+1 \leq k_1+1 \leq r-1 \leq r$，因此根据四边形不等式有

    $$
    f_{u+1,r-1} + f_{k_1+1,r} \leq f_{u+1,r} + f_{k_1+1,r-1}
    $$

    再根据 $u$ 是状态 $f_{l,r}$ 的最优决策点可知

    $$
    f_{l,u} + f_{u+1,r} \leq f_{l,k_1} + f_{k_1+1, r}
    $$

    将以上两个不等式相加，得

    $$
    f_{l,u} + f_{u+1,r-1} \leq f_{l,k_1}+f_{k_1+1,r-1}
    $$

    即 $g_{u,l,r-1} \leq g_{k_1,l,r-1}$，但这与 $k_1$ 是最小的最优决策点矛盾，因此 $k_1\leq u$。

  2. 若 $u>k_2$，则 $l\leq l+1 \leq k_2\leq u$，根据四边形不等式可得

    $$
    f_{l,k_2} + f_{l+1,u} \leq f_{l,u} + f_{l+1, k_2}
    $$

    再根据 $k_2$ 是状态 $f_{l+1, r}$ 的最优决策点可知

    $$
    f_{l+1,k_2} + f_{k_2+1, r} \leq f_{l+1,u} + f_{u+1,r}
    $$

    将以上两个不等式相加，得

    $$
    f_{l,k_2}+f_{k_2+1,r} \leq f_{l,u} + f_{u+1,r}
    $$

    即 $g_{k_2,l,r} \leq g_{u,l,r}$，但这与 $u$ 是最小的最优决策点矛盾，因此 $u \leq k_2$。

因此，如果在计算状态 $f_{l,r}$ 的同时将其最优决策点 $m_{l,r}$ 记录下来，那么我们对决策点 $k$ 的总枚举量将降为

$$
\sum_{1\leq l<r\leq n} m_{l+1,r} - m_{l,r-1} = \sum_{i=1}^n m_{i,n} - m_{1,i}\leq n^2
$$

怎样使用四边形不等式

合并石子问题

题目描述

在一个操场上摆放着一排 $N$ 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的 $2$ 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。

试设计一个算法，计算出将 $N$ 堆石子合并成一堆的最小得分。

输入格式

第一行一个整数 $N$。

接下来 $N$ 行，第 $i$ 行一个整数 $a_i$
​
，代表第 $i$ 堆石子的石子数。

输出格式

输出将所有石子合并为一堆的最小得分。

输入输出样例

输入 #1

1
2
3
4
5
4
1
1
1
1

输出 #1

1
8

说明/提示

$$
N \leq 4000, a_i \leq 200
$$

很容易想到这样一个dp转移

1
dp[i][j]=min{dp[i][k]+dp[k+1][j]}+cost[i][j]

很明显这个式子和开始的那个式子是相同的，这就要用到我们的四边形不等式优化了。

首先容易发现，在这个题目中，$w(l,r)$就是$l到r$所有的石子数量，是固定的，所以它显然满足四边形不等式。

我们前面的推导就派上用场了。

原来的代码：

1
2
3
4
for(register int i=n-1; i>=1; --i)
	for(register int j=i+1; j<=n; ++j)
		for(register int k=i; k<=j-1; ++k)
			dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+a[j]-a[i-1]);

现在：

1
2
3
4
5
6
7
8
9
10
for (int len = 2; len <= n; ++len)  // 枚举区间长度
  for (int l = 1, r = len; r <= n; ++l, ++r) {
    // 枚举长度为len的所有区间
    f[l][r] = INF;
    for (int k = m[l][r - 1]; k <= m[l + 1][r]; ++k)
      if (f[l][r] > f[l][k] + f[k + 1][r] + w(l, r)) {
        f[l][r] = f[l][k] + f[k + 1][r] + w(l, r);  // 更新状态值
        m[l][r] = k;  // 更新（最小）最优决策点
      }
  }

很明显，k不用每一次都从头试到尾了。

这样子，均摊复杂度大概可以到$O(n^2)$了，能过掉我写在这里的这一道合并石子了。