四边形不等式学习笔记

　　四边形不等式是一种动态规划的优化方法，通常利用其来证明决策单调性，以优化动态规划的时间复杂度(减少枚举决策点的时间从而降一个时间维度)。　　

一，四边形不等式：

前置说明：\(w(l, r)\)是区间\([l,r]\)上的权值函数，可以理解为dp转移边上的边权，即转移一步的花费。

定义：

（1）区间包含单调性：若 \(l \le l' \le r'\le r\) 且 \(w(l',r') \le w(l,r)\)，则称函数 \(w(l,r)\) 具备区间包含单调性。

（2）四边形不等式：若对任意的 \(l_1 \le l_2 \le r_1 \le r_2\) 有 \(w(l_1, r_1) + w(l_2,r_2) \le w(l_1, r_2) + w(l_2, r_1)\)，则称函数 \(w(l,r)\) 满足四边形不等式。

四边形不等式判定定理：

• 若对于任意 \(a

证明（采用数学归纳法）：

(1) 注意定义给出的条件a和a+1，b和b+1，说明：当 \(l_1 + 1 = l_2\) 且 \(r_1 + 1 = r_2\) 成立时，函数 \(w\) 满足四边形不等式关系。

(2) 根据 (1) 来证明，当 \(l_1 + k = l_2\) 且 \(r_1 + 1= r_2\) 成立时，函数 \(w\) 仍满足四边形不等式关系。

　对于任意 \(a+1 < c\) 有 \(w(a,c)+w(a+1,c+1)\le w(a,c+1)+w(a+1,c)\) ①

　同时写出 \( w(a+1, c) + w(a+2, c+1) \le w(a+1, c+1) + w(a+2,c)\) ② 这里\(a+2=c\)都没关系了，一般\(w(i,i)\)都会设置为0或者其它特殊常数。

　①+②得：\(w(a,c)+w(a+2,c+1)\le w(a,c+1)+w(a+2,c)\) 

　从而通过两个\(l_1+1=l_2\)的式子构建出\(l_1+2=l_2\)的式子，同理对于任意的正整数k，\(l_1+k=l_2\)都满足四边形不等式。

(3) 我们发现在上述构造过程中， \(l_1+k_l=l_2\) 和 \(r_1+k_r=r_2\) 两个条件相互独立。所以通过(2)的证明，\(r_1+k=r_2\)也都满足四边形不等式。

最后，对于任意的 \(l_1\le l_2 \le r_1 \le r_2\) 都满足四边形不等式。

下面我们来探讨如何利用上面的四边形不等式来优化一些递推方程。 

二，一维线性DP优化

线性递推式：\(dp_i = min_{j

• 定理： 当\(w\)函数满足四边形不等式时，\(dp\)函数满足决策单调性。

一些假设：

　设\(p_i\)为\(dp_i\)的决策点，\(p_{i-1}\)是\(dp_{i-1}\)的决策点。

证明（采用反证法）：

　\(p_i\)是i的决策点，而\(p_{i-1}\)是i-1的决策点，我们要证明的是：\(p_{i-1} \le p_i\)

　我们现在假设：\(p_i \lt p_{i-1} \lt i-1 \lt i\)。

　① \(dp_{p_i} + w(p_i, i) \le dp_{p_{i-1}} + w(p_{i-1}, i)\) 因为\(p_i\)是i的最小决策点。

　② \(w(p_i, i-1) + w(p_{i-1}, i) \le w(p_i, i) + w(p_{i-1}, i-1)\) 这一步是根据\(w\)的四边形不等式。

　①+②得：\(dp_{p_i} + w(p_i, i-1) \le dp_{p_{i-1}} + w(p_{i}, i-1)\) 这说明 \(p_i\)才是i-1的决策点，与假设相矛盾。

所以证明出如果\(p_{i-1}\)是i-1的决策点，\(p_i\)是i的决策点，那么\(p_i\)一定大于等于\(p_{i-1}\)。

根据决策点的单调性，我们可以使用单调队列+二分快速得出决策点。

例题：CF321E Ciel and Gondolas 使用wqs二分 + \(w\)函数四边形不等式的决策单调性 \(O(n*logn*logW)\)，W是值域。

三，二维DP优化

类型一：区间递推DP \(F_{l,r} = \min_{l\le k\lt r}\space\{F_{l,k}+F_{{k+1},r}\}+w(l,r)\) 

类型二：序列划分DP \(F_{k,i} = \min_{j < i}\space\{F_{k-1,j} + w(j, i)\} \) k一般代表序列划分成k段 

首先直接给出2个定理：

• 定理1：如果\(w\)函数满足1.区间包含单调性、2.四边形不等式，那么\(F\)函数满足四边形不等式
• 定理2：如果\(F\)函数满足了四边形不等式，定义\(P_{l,r}\)为\(F[l][r]\)的决策点，那么有： \(P_{l,r-1} \le P_{l,r} \le P_{l+1,r}\)

类型一的证明可以在OI-WIKI[参考资料(2)]找到，而且较详细，把关注点放在第二类。（参照文章底下[参考资料(1)]的证明过程）

类型二的四边形不等式感觉不如第一类那么直观，因为有一维表示划分了多少段，而另一维是序列[1:i]。（写到这里时，我还是不能直接理解）

先证明定理一：

假设函数\(w\)满足四边形不等式以及区间包含单调性，以及\(P[i][j]\)是\(F[i][j]\)的最优决策点。

(1) 当i==j时，\(0+0=F[i][i]+F[i+1][i+1] \le F[i][i+1] + F[i+1][i] = F[i][i+1] + 0\)（假设f[i][i]=0，且非法状态都是0）

(2) 当i分两种情况：

　第一种：\(i-1\le x \le y \le j\)\begin{align*}F[i][j]+F[i+1][j+1] &\le F[i-1][x]+W(x,j)+F[i][y]+W(y,j+1) \\ &\le F[i-1][x]+W(x,j+1)+F[i][y]+W(y,j) = F[i][j+1]+F[i+1][j]\end{align*}

　第二种：\(i \le y < x < j\)\begin{align*}F[i][j]+F[i+1][j+1] &\le F[i-1][y]+W(y,j)+F[i][x]+W(x,j+1)\\&\le F[i-1][y]+W(y,j+1)+F[i][x]+W(x,j)=F[i][j+1]+F[i+1][j]\end{align*}

参考资料：

（1）四边形不等式-a1b3c7d9 强推这篇，写得超级好

（2）OI-WIKI - 有较多的证明以及应用

（3） - 有些证明的思路较巧妙

（4）四边形不等式 罗勇军 

（5）四边形不等式学习笔记 - 学会打表验证

（6）赵爽的论文 

（7）四边形不等式讲解