四边形不等式

四边形不等式用于区间$dp$，对于$dp$方程（注意如果额外代价和$k$有关好像是不行的...）：

$$d{p}_{i,j}=\underset{k=i}{\overset{j-1}{min}}\{d{p}_{i,k}+d{p}_{k+1,j}\}+w_{i,j}$$

如果$\mathrm{\forall }a<b\le c<d$，都有$w_{a,c}+w_{b,d}\le w_{b,c}+w_{a,d}$，那么就可以用四边形不等式把复杂度从$O(n^3)$优化到$O(n^2)$。

具体操作是：对于$\mathrm{\forall }i,j$，设$po{s}_{i,j}$是使$d{p}_{i,j}$取到最优值的$k$，则有$po{s}_{i,j-1}\le po{s}_{i,j}\le po{s}_{i+1,j}$。然后在这个范围内暴力循环$k$，是$O(n^2)$的。

真正做题的时候可以先暴力区间$dp$，然后发现它是满足上述单调性的就好了。

证明待填坑。