四边形不等式优化

最近刚好在学 dp 优化，感觉这个证明还是蛮有意思的，分享分享。

问题 & 转移方程

有 $n$ 堆石子排成一行，现在要你进行 $n-1$ 次合并操作，每次将相邻的两堆石子合成一堆，代价为两堆石子数只和。要求最小化 $n-1$ 次合并操作的代价之和。

容易推出转移方程：

$$f(i,j)=\min_{i\le k\lt j}f(i,k)+f(k+1,j)+w(i,j)$$

。我们知道这是一个 2d1d 区间 dp，可以用 $\Theta(n^3)$ 解决。但是有没有更快的方法呢？

更快的解法？

设 $\text{opt}(i,j)$ 为 $k$ 使得 $f(i,j)=f(i,k)+f(k+1,j)+w(i,j)$，这里 $\text{opt}$ 即 $(i,j)$ 的最优转移点。那么有 $\text{opt}(i,j-1)\le\text{opt}(i,j)\le\text{opt}(i+1,j)$。显然，当 $j-i$ 相同时，对于每一个不同的 $i$，$\text{opt}(i,j)$ 是单调的，也就是自动隐去了 $\text{opt}(i,j)$ 独占一维的影响，宏观上看消去了转移的一维，时间复杂度变成 $\Theta(n^2)$。

问题来了，我们的做法基于 $\text{opt}(i,j-1)\le\text{opt}(i,j)\le\text{opt}(i+1,j)$ 这个不等式，即决策单调性，那么该转移式的决策单调性怎么来的呢？不着急着直接证明单调性，先引入几个前置内容。

$\text{Monge}$ 数组 & 四边形不等式

对于 $n*m$ 的矩阵 $A$，对于任意 $1\le i\le j\le n,1\le k\le p\le m$，有 $A_{i,k}+A_{j,p}\le A_{i,p}+A_{j,k}$。这个不等式又称作四边形不等式。

对于四边形不等式，有一个等价的形式即 $A_{i,k}+A_{i+1,k+1}\le A_{i,k+1}+A_{i+1,k}$。接下来来证明为什么是等价的。

---

证明：

对于必要性，显然 $A_{i,k}+A_{i+1,k+1}\le A_{i,k+1}+A_{i+1,k}$ 是 $A_{i,k}+A_{j,p}\le A_{i,p}+A_{j,k}$ 一种特殊形式，即 $j=i+1,p=k+1$ 的特殊情况。所以必要性显然。

证明充分性。对于 $A_{i,k}+A_{i+1,k+1}\le A_{i,k+1}+A_{i+1,k}$ 移项过去成 $A_{i+1,k+1}-A_{i+1,k}\le A_{i,k+1}-A_{i,k}$。同理可得 $A_{i+1,k+2}-A_{i+1,k+1}\le A_{i,k+2}-A_{i,k+1}$，两个式子并起来成 $A_{i+1,k+2}-A_{i+1,k}\le A_{i,k+2}-A_{i,k}$。可以扩展到 $A_{i+1,k+p}-A_{i+1,k}\le A_{i,k+p}-A_{i,k}$。同样地，扩展到第二维，并把它一般化为 $A_{i,k}+A_{j,p}\le A_{i,p}+A_{j,k}$，得到充分性。

证毕。

---

那么，例题的转移方程和四边形不等式有什么关系呢？

证明 $w,f$ 均满足四边形不等式

显然，我们的价值函数 $w(i,j)=\sum_{1\le p\le j}a_p-\sum_{1\le p\lt i}a_p$ 满足四边形不等式。因为它满足 $A_{i,k}+A_{i+1,k+1}\le A_{i,k+1}+A_{i+1,k}$。有一些常见的满足四边形不等式的价值函数，这里罗列一下：

• $w(l,r)=\sum_{l\le i\le r}a_i$
• $w(l,r)=(r-l+1)^k(k\in\Z^+)$
• $w(l,r)=f(r)-f(l-1)$
• $w(l,r)=f(l-1)+g(r)$
• $w(l,r)=f(r-l+1)$ 且 $f(i)$ 满足离散凸性

。$w$ 函数满足四边形不等式，且满足区间单调性（注意一定要有区间单调性，反例是 $w(l,r)=l-r$）即 $w(a,d)\ge w(b,c),a\le b\le c\le d$。那么如何来证明 $f$ 是否满足四边形不等式呢？

考虑归纳证明。对于 $f(i,i)=0$，显然满足四边形不等式。对于 $f(i,j)$，假设 $j-i+1<len_0$ 的已经被证明满足四边形不等式，那么此时仅需证明 $f(i,j-1)+f(i+1,j)\le f(i+1,j-1)+f(i,j)$ 即可。设 $C=\text{opt}(i+1,j-1),D=\text{opt}(i,j)$，假设 $C\le D$，不失一般性，则显然有

$$f(i,j-1)+f(i+1,j)\le f(i,C)+f(C+1,j-1)+f(i+1,D)+f(D+1,j)$$

。由于前面的归纳且已知 $D\lt j$，所以

$$f(i,C)+f(i+1,D)\le f(i+1,C)+f(i,D)$$

。推出

$$f(i,C)+f(C+1,j-1)+f(i+1,D)+f(D+1,j)\le f(i+1,C)+f(C+1,j-1)+f(i,D)+f(D+1,j)$$

。进一步得到

$$f(i,j-1)+f(i+1,j)\le f(i+1,j-1)+f(i,j)$$

。所以我们成功证明了 $f$ 也满足四边形不等式。区间单调性易证。

$\text{Knuth}$ 定理：证明 $\text{opt}$ 满足决策单调性

我们同样用归纳证明。对于区间 $(i,j)$，设 $p=\text{opt}(i,j-1),q=\text{opt}(i+1,j)$。$j-i=0$ 显然满足决策单调性。设所有 $j-i$ 较小的已经全部证明决策单调性。

证明 $\lt p$ 的转移不会更优，对于 $\gt q$ 的部分对称同理。找到一个 $i\le pos\lt p$，有

$$f(pos,j-1)+f(p,j)\le f(pos,j)+f(p,j-1)$$

$$f(p,j)-f(p,j-1)\le f(pos,j)-f(pos,j-1)$$

。说明转移点 $pos$ 在右端点 $j-1$ 扩展到 $j$ 转移所花代价更大，肯定不优。证毕。

综上所述，我们通过先证明 $w,f$ 满足四边形不等式、区间单调性，再利用 $\text{Knuth}$ 定理证明了转移式满足决策单调性，把 2d1d 的转移优化到 $\Theta(n^2)$，这就是四边形不等式优化。