四边形不等式优化

四边形不等式与蒙日矩阵

首先讲一下这玩意的用处，个人认为这是在理解四边形不等式优化中最能引入的点：限制状态的枚举，也就是所谓的决策单调性（看起来像废话因为所有优化都是在限制枚举的范围）

对不同类型的$dp$，如果它的状态转移满足四边形不等式，其实我们都可以以某种方式得到决策单调性，所以尽管下面讲的证明比较具有局限性，但是他的应用往往是需要一些想像力的。

设 $w_{x,y}$ 为定义在整数集合上的二元函数。若 $\forall l\le l'\le r'\le r : w_{l,r'}+w_{l',r}\le w_{l,r}+w_{l',r'}$ ，可记作交叉小于包含，则称函数 $w_{x,y}$ 满足四边形不等式。

事实上，对于一个二元函数是否满足四边形不等式可以通过更简便的方法证明：

设 $w_{x,y}$ 为定义在整数集合上的二元函数。若 $\forall l\lt r : w_{l,r+1}+w_{l+1,r}\le w_{l,r}+w_{l+1,r+1}$ ，则称函数 $w_{x,y}$ 满足四边形不等式。

正确性的证明如下：

$\forall a\lt c:w_{a,c}+w_{a+1,c+1}\le w_{a+1,c}+w_{a,c+1}$

$\forall a+1\lt c:w_{a+1,c}+w_{a+2,c+1}\le w_{a+1,c+1}+w_{a+2,c}$

两式相加，可得

$w_{a,c}+w_{a+2,c+1}\le w_{a+2,c}+w_{a,c+1}$

以类似第二个式子的方法，可以以不断加的方法把a这一边推广至：

$\forall a\le b\le c:w_{a,c}+w_{b,c+1}\le w_{b,c}+w_{a,c+1}$

用同样的方法也可以扩展c这一边至：

$\forall a\le b\le c\le d:w_{a,c}+w_{b,d}\le w_{b,c}+w_{a,d}$

证毕。

（下面的证明会用到一些式子的合并以及非等量但是满足单调性的代换，比上面的更复杂一点，请注意其运用）

1D/1D dp的优化

笔者其实并不知道什么是1D/1D dp，可能是一维dp吧

对于某些形如：

$f_{i}=\min_{j=1}^{i}(f_j+w_{j,i})$

的$dp$，设对于一个位置 $i$，他的最优决策选取的位置为 $k_{i}$，如果 $w_{i,j}$ 满足四边形不等式，则有

$\forall i\le j : k_i\le k_j$

证明:
假设 $\forall i\le j :k_j\lt k_i$ ,那么 $k_j\lt k_i\lt i\le j$ ,根据四边形不等式有：

$w_{k_j,i}+w_{k_i,j}\le w_{k_j,j}+w_{k_i,i}$

又因为 $k_j$ 是 $j$ 的最优决策点，所以有：

$f_{k_j}+w_{k_j,j}\le f_{k_i}+w_{k_i,j}$

两式相加，可得：

$f_{k_j}+w_{k_j,i}\le f_{k_i}+w_{k_i,i}$

这也就与 $k_i$ 为 $i$ 的最优决策点相冲突，
因此 $k_i$ 必然小于 $k_j$ 。

证毕。

那么既然知道了最优决策点的位置的单调性，我们便可以在每一次遍历到新的下标 $i$ 时，利用二分找到以自己为最优决策点的最靠前的位置并更新后面的全部，这样时间复杂度就从$\Theta(n^2)$变为了$\Theta(n\log n)$

2D/1D dp的优化

然而笔者也不知道什么是2D/1D dp，或许可以理解为二维的dp吧

对于经典的区间$dp$，我们往往需要枚举区间左右端点和中间的断点，那它的复杂度自然就是显而易见的$\Theta(n^3)$

然而有些时候，你会发现这个三次方是过不了的，可能需要消掉一个$n$，在这种情况下，我们可以考虑去证明他的决策单调性（如果你对证明有疑问，大可先去看看结论起的用处再回来看证明）OIwiki

再引入一个概念：

区间包含单调性：若对于任意的 $l\le l'\le r'\le r$ ，满足 $w_{l',r'}\le w_{l,r}$ 则称 $w_{l,r}$ 满足区间包含单调性。

总结

其实我们真正在使用四边形不等式优化的时候，首先是要想到他最开始的状态转移方程，由于很有可能有多种非正解的设计方式，所以我们其实应该不止揪着一种去想他的优化~~（头够铁也未必不行），多设计几种，看看那种类似我们提到过的模型，再试一试证明它的取值函数满足四边形不等式（哪怕是打个表看看是否满足决策单调性）~~，如果可以，而时间复杂度又符合，那肯定就做完了$qwq$