省选算法学习-dp优化-四边形不等式

嗯......四边形不等式的确长得像个四边形【雾】

我们在dp中，经常见到这样一类状态以及转移方程：

设$dp\left[i\right]\left[j\right]$表示闭区间$\left[i,j\right]$中的最小值/最大值/和值

然后有这样的转移：

$dp\left[i\right]\left[j\right]=min\left(dp\left[i\right]\left[k-1\right]+dp\left[k\right]\left[j\right]+w\left(i,j\right)\right)$，其中$i<k\leqslant j$

$w\left(i,j\right)$表示闭区间$\left[i,j\right]$通过一定方法计算出来的费用

这个dp的复杂度显然是$O\left(n^3\right)$的，因为是平方的状态、线性的转移

但是有的时候这样的复杂度并不够切掉题目，这时我们需要一些优化

那么在这种情况下，四边形不等式就可以发挥它的价值了

首先，定义区间单调性如下：

当$p_1\leqslant p_2\leqslant p_3\leqslant p_4$时，若$w\left(p_2,p_3\right)\leqslant w\left(p_1,p_4\right)$，则称$w$满足区间单调性

同时定义四边形不等式如下：

当$p_1\leqslant p_2\leqslant p_3\leqslant p_4$时，若$w$满足如下式子，则称$w$满足四边形不等式：

$w\left(p_1,p_3\right)+w\left(p_2,p_4\right)\leqslant w\left(p_2,p_3\right)+w\left(p_1,p_4\right)$

接下来是一条非常重要的定理：

如果$w$函数满足四边形不等式，那么$dp$函数也满足四边形不等式！

也就是说：

当$p_1\leqslant p_2\leqslant p_3\leqslant p_4$时

$dp\left(p_1,p_3\right)+dp\left(p_2,p_4\right)\leqslant dp\left(p_2,p_3\right)+dp\left(p_1,p_4\right)$

而且还有另一个定理：

如果$dp$函数满足四边形不等式，那么表示$dp$函数取得最优值的点（也就是k）的那个函数$s$在每一行和每一列上单调

这个有点绕，换种说法

设$s\left[i\right]\left[j\right]$表示当$dp\left[i\right]\left[j\right]=min\left(dp\left[i\right]\left[k-1\right]+dp\left[k\right]\left[j\right]+w\left(i,j\right)\right)$的时候

$dp\left[i\right]\left[j\right]$取到最优（比如最大最小）值的时候，$k$的值，

那么$s$函数满足：

$s\left[i\right]\left[j\right]\leqslant s\left[i\right]\left[j+1\right]$，且$s\left[i\right]\left[j\right]\leqslant s\left[i+1\right]\left[j\right]$

也就是说在枚举$k$值的时候，我们的闭区间变成了$\left[s\left[i\right]\left[j-1\right],s\left[i+1\right]\left[j\right]\right]$

因此只要先枚举区间长度，再枚举$i$求出$j$，就可以利用这个优化了

这个优化用完了以后，总复杂度可以从$O\left(n^3\right)$变成$O\left(n^2\right)$的

美滋滋