学习笔记 - 四边形不等式的理论证明

老师讲课就让背结论……不管，还是要知道四边形不等式为什么正确！

参考 OI wiki

# 区间DP的四边形不等式

对于区间 $(l,r)$，它的DP值为 $f(l,r)$，代价为 $c(l,r)$。
有转移式 $f(l,r)=f(l,k)+f(k+1,r)+c(l,r)$。

如果对于任意 $l_1\leq l_2\leq r_1\leq r_2$ 都有：

区间包含的单调性：$c(l_2,r_1)\leq c(l_1,r_2)$；（因为区间 $(l_2,r_1)\subseteq (l_1,r_2)$）
“交叉小于包含”：$c(l_1,r_1)+c(l_2,r_2)\leq c(l_1,r_2)+c(l_2,r_1)$；

那么存在四边形不等式：$f(l_1,r_1)+f(l_2,r_2)\leq f(l_1,r_2)+f(l_2,r_1)$。

- 证明

首先假设四边形不等式成立：

令 $l_1\leq l_2\leq r_1\leq r_2$，且满足：

$c(l_2,r_1)\leq c(l_1,r_2)$；
$c(l_1,r_1)+c(l_2,r_2)\leq c(l_1,r_2)+c(l_2,r_1)$；
$f(l_1,r_1)+f(l_2,r_2)\leq f(l_1,r_2)+f(l_2,r_1)$。

设 $u,v$ 分别表示 $f(l_1,r_2),f(l_2,r_1)$ 的最优决策点。

若 $u\leq v$，则 $l_1\leq u\leq v<r_1\leq r_2$；所以 $u+1\leq v+1\leq r_1\leq r_2$。
$\therefore \begin{matrix} f(l_1,r_1)\leq f(l_1,u)+f(u+1,r_1)+c(l_1,r_1)&&(1)\\ f(l_2,r_2)\leq f(l_2,v)+f(v+1,r_2)+c(l_2,r_2)&&(2) \end{matrix}$

> Hint

$u,v$ 是 $f(l_1,r_2),f(l_2,r_1)$ 的最优决策点，但不一定是 $f(l_1,r_1),f(l_2,r_2)$ 的最优决策点。因此是 “$\leq$”

$\begin{matrix} \because u+1\leq v+1\leq r_1\leq r_2\\ \therefore f(u+1,r_1)+f(v+1,r_2)\leq f(u+1,r_2)+f(v+1,r_1) &&(3) \end{matrix}$
由 (1)+(2) ：$f(l_1,r_1)+f(l_2,r_2)\leq f(l_1,u)+f(u+1,r_1)+c(l_1,r_1)+f(l_2,v)+f(v+1,r_2)+c(l_2,r_2)$
代入 (3) ：$f(l_1,r_1)+f(l_2,r_2)\leq f(l_1,u)+f(u+1,r_2)+c(l_1,r_1)+f(l_1,v)+f(v+1,r_1)+c(l_2,r_2)$

因为 $c(l_1,r_1)+c(l_2,r_2)\leq c(l_1,r_2)+c(l_2,r_1)$；
所以 $f(l_1,r_1)+f(l_2,r_2)\leq f(l_1,u)+f(u+1,r_2)+c(l_1,r_2)+f(l_1,v)+f(v+1,r_1)+c(l_2,r_1)$

因为 $u,v$ 分别是 $f(l_1,r_2),f(l_2,r_1)$ 的最优决策点；
$\therefore\begin{matrix} f(l_1,r_2)=f(l_1,u)+f(u+1,r_2)+c(l_1,r_2)\\ f(l_2,r_1)=f(l_2,v)+f(v+1,r_1)+c(l_2,r_1) \end{matrix}$
代入可得 $f(l_1,r_1)+f(l_2,r_2)\leq f(l_1,r_2)+f(l_2,r_1)$；

得证。
若 $v<u$，则 $l_1\leq l_2\leq v<u\leq r_2$；
$\therefore \begin{matrix} f(l_1,r_1)\leq f(l_1,v)+f(v+1,r_1)+c(l_1,r_1)&&(4)\\ f(l_2,r_2)\leq f(l_2,u)+f(u+1,r_2)+c(l_2,r_2)&&(5) \end{matrix}$
因为 $l_1\leq l_2\leq v<u$；
所以 $f(l_1,v)+f(l_2,u)\leq f(l_1,u)+f(l_2,v) (6)$；

由 (4)+(5)：$f(l_1,r_1)+f(l_2,r_2)\leq f(l_1,v)+f(v+1,r_1)+c(l_1,r_1)+f(l_2,u)+f(u+1,r_2)+c(l_2,r_2)$
代入 (6)：$f(l_1,r_1)+f(l_2,r_2)\leq f(l_1,u)+f(u+1,r_2)+f(l_2,v)+f(v+1,r_1)+c(l_1,r_1)+c(l_2,r_2)$

因为 $c(l_1,r_1)+c(l_2,r_2)\leq c(l_1,r_2)+c(l_2,r_1)$
所以 $f(l_1,r_1)+f(l_2,r_2)\leq f(l_1,u)+f(u+1,r_2)+f(l_2,v)+f(v+1,r_1)+c(l_1,r_2)+c(l_2,r_1)$

也就是 $f(l_1,r_1)+f(l_2,r_2)\leq f(l_1,r_2)+f(l_2,r_1)$；

得证。

- 决策单调性

对于DP状态 f[l][r] 表示区间 $[l,r]$ 的总代价，若转移式如下面形式：f[l][r]=min/max{f[l][k]+f[k+1][r]+cst(l,r)}，且 cst(l,r) 满足四边形不等式。

根据之前的证明，可知 f[l][r] 也满足四边形不等式。还有一个结论——记 t[l][r] 表示 f[l][r] 的所有最优决策点中最小的一个，则有 t[l][r-1]<=t[l][r]<=t[l+1][r]

不妨设 f[l][r] 取 min（取 max 一样的），证明如下：

记 a=f[l][r-1],b=f[l][r],c=f[l+1][r]（$l\le a<r-1,l\le b<r,l+1\le c<r$）

则需证明 $a\le b\le c$，考虑反证法：

假设 $a>b$：

则 $b+1\le a+1\le r-1< r$，根据“交叉小于包含”：
$f_{b+1,r-1}+f_{a+1,r} \le f_{b+1,r}+f_{a+1,r-1}$
又因为 $b$ 是 f[l][r] 的最优决策点：
$f_{l,b}+f_{b+1,r} \le f_{l,a}+f_{a+1,r}$
两式相加可得：
$f_{b+1,r-1}+f_{a+1,r}+f_{l,b}+f_{b+1,r}\le f_{b+1,r}+f_{a+1,r-1}+f_{l,a}+f_{a+1,r}\\ f_{b+1,r-1}+f_{l,b}\le f_{a+1,r-1}+f_{l,a}$
也就是说 f[l][r-1] 通过 b 来转移不会比 a 差，与 a 是最小的最优决策点矛盾。
假设 $b>c$：

那么 $l<l+1<c\le b$，根据“交叉小于包含”：
$f_{l,c}+f_{l+1,b}\le f_{l,b}+f_{l+1,c}$
又因为 $c$ 是 f[l+1][r] 的最优决策点：
$f_{l+1,c}+f_{c+1,r}\le f_{l+1,b}+f_{b+1,r}$
两式相加可得：
$f_{l,c}+f_{l+1,b}+f_{l+1,c}+f_{c+1,r}\le f_{l,b}+f_{l+1,c}+f_{l+1,b}+f_{b+1,r}\\ f_{l,c}+f_{c+1,r}\le f_{l,b}+f_{b+1,r}$
也就是说 f[l][r] 通过 c 来转移不会比 b 差，与 b 是 f[l][r] 的最小的最优决策点矛盾。

于是得证。

# 阶段性DP的决策单调性

对于一类DP：f[i][j] 表示第 j 个阶段、状态 i 的最优值。

比如“把n个数分为连续的m段，求每一段异或之和的最小值”，定义 f[i][j] 表示“前 i 个数分了 j 段”，换句话说就是“在 ‘分了 j 段’ 这个阶段下，状态为 ‘前 i 个数’ 的最小值”。

from SPOJ - Ada and Mold

为什么叫“阶段性”？观察其转移式，可以找到如下模型：

1	f[i][j]=min/max{f[k][j-1]+w(k+1,i)}

因此 f[][j] 只与 f[][j-1] 有关，即只与上一个阶段有关。

- 结论

定义 p(i,j) 为 f[i][j] 的最小的最优转移点。

若 w(l,r) 满足四边形不等式，则 $p(i,j-1)\le p(i,j)\le p(i+1,j)$，因此可以用类似区间DP的方法优化。

- 证明

设 $a,b,c$ 分别为 $p(i,j-1),p(i,j),p(i+1,j)$。仍然考虑反证：

假设 $b<a$，则 $b<a\le j-1<j$：
$f(i,b)+w(b,j)\le f(i,a)+w(a,j)$
根据 $w(l,r)$ 的四边形不等式：
$w(b,j-1)+w(a,j)\le w(b,j)+w(a,j-1)$
两式相加：
$f(i,b)+w(b,j-1)\le f(i,a)+w(a,j-1)$
于是得到如果 f[i][j-1] 通过 b 转移会比 a 转移优……然后就推出矛盾了。于是 $a\le b$。
假设 $c<b$，则 $c<b\le j\le j+1$：

根据 $w(l,r)$ 的四边形不等式：

两式相加：

也就是说 f[i][j+1] 用 c 转移会比用 b 优。但是根据之前证明的 “$a\le b$”：$p(i,j)\le p(i,j+1)$
```
推出矛盾，所以 $b\le c$
```

得证。

The End

Thanks for reading!

这篇博客是 2019.12.8 开始写的……咕了好久了