初探四边形不等式
对于$a<c$，$w_{a,c+1}+w_{a+1,c}\ge w_{a,c}+w_{a+1,c+1}$
对于$a<c+1$，$w_{a+1,c+1}+w_{a+2,c}\ge w_{a+1,c}+w_{a+2,c+1}$
两式相加，有
$w_{a,c+1}+w_{a+1,c}+w_{a+1,c+1}+w_{a+2,c}\ge w_{a,c}+w_{a+1,c+1}+w_{a+1,c}+w_{a+2,c+1}$
减掉重的部分，有
$w_{a,c+1}+w_{a+2,c}\ge w_{a,c}+w_{a+2,c+1}$
以此类推，有
$a\le b\le c,w_{a,c+1}+w_{b,c}\ge w_{a,c}+w_{b,c+1}$
$a\le b\le c\le d,w_{a,d}+w_{b,c}\ge w_{a,c}+w_{b,d}$(四边形不等式的定义)
一维线性DP的四边形不等式优化
记$p_i$为$f_i$的最优决策，即$f_i=f_{p_i}+val_{p_i,i}$，若在$p$在$[1,N]$中单增不减，即可说明$f$具有单调性。
决策具有单调性
在状态转移方程中$f_i=\min\limits_{0\le j<i}\{f_j+val_{j,i}\}$中，若函数(或变量)$val_{j,i}$满足四边形不等式，则$f$具有单调性。
证明:
$\forall i\in[1,N],\forall j\in[0,p[i]-1]$，根据$p_i$的最优性，有:
$\large f_{p_i}+val_{p_i,i}\le f_j+val_{j,i}$
$\forall i'\in(i,N]$，由于$val$满足四边形不等式，有:
$\large val_{j,i'}+val_{p_i,i}\ge val_{j,i}+val_{p_i,i'}$
$\large val_{p_i,i'}-val_{p_i,i}\le val_{j,i'}-val_{j,i}$
两式相加有:
$\large f_{p_i}+val_{p_i,i'}\le f_{j}+val_{j,i'}$
得证。
因此，对于$\forall i\in[1,N],\forall j\in[0,p[i]-1] ,j$在所有未来状态下，都没有比$p_i$更加优秀。
换言之，对于未来状态的最优决策，一定不小于$p_i$,即$p_{i'}\ge p_i$。
关于具体的做法，就用一个队列开个三元组$(l,r,p)$单调维护就好了，检查队尾，对于左端点的解都大于当前的值的解，那么直接删去这个三元组，对于右端点都小于的，新开一个三元组$(r+1,n,i)$推进队列里，对于其他情况，得二分找到位置。
二维区间DP的四边形不等式优化
对于$\large f_{i,j}=\min\limits_{i\le k<j}\{f_{i,k}+f_{k+1,j}+w_{i,j}\}$(特别地，$f_{i,i}=w_{i,i}=0$)，如果下面两个条件成立:
- $w$满足四边形不等式
- 对于任意的$a\le b\le c \le d$，有$w_{a,d}\ge w_{b,c}$。
那么$f$也满足四边形不等式，也就是需要证明$\large f_{i,j+1}+f_{i+1,j}\ge f_{i,j}+f_{i+1,j+1}$。
证明:
- 当$i+1=j$时，$\large f_{i,j+1}+f_{i+1,j}=f_{i,i+2}+f_{i+1,i+1}=f_{i,i+2}$
- $f_{i,i+2}$的最优决策为$i+1$，即$f_{i,j+1}=f_{i,i+2}=f_{i,i+1}+f_{i+2,i+2}+w(i,i+2)=w_{i,i+1}+w_{i,i+2}\ge w_{i,i+1}+w_{i+1,i+2}=f_{i,i+1}+f_{i+1,i+2}=f_{i,j}+f_{i+1,j+1}$
通过上述第二个条件可以得到。
- 同理，$f_{i,i+2}$的最优决策为$i$，即
$f_{i,j+1}=f_{i,i+2}=f_{i,i}+f_{i+1,i+2}+w_{i,i+2}=w_{i+1,i+2}+w_{i,i+2}\ge w_{i+1,i+2}+w_{i,i+1}=f_{i+1,i+2}+f_{i,i+1}=f_{i+1,j+1}+f_{i,j}$
- 故当$i+1=j$时，四边形不等式对$f_{i,j}$成立。
- 接下来用数学归纳法。假设当$i+k<j$时，四边形不等式对$f_{i,j}$成立。考虑$i+k=j$的情况，假设$f_{i,j+1}$以$x$为最优决策，$f_{i+1,j}$以$y$为最优决策，不妨设$i+1\le x\le y$
- 那么有$f_{i+1,j}+f_{i,j+1}=f_{i+1,x}+f_{x+1,j}+w_{i+1,j}+f_{i,y}+f_{y+1,j+1}+w_{i,j+1}$
- 对于$f_{i,j}+f_{i+1,j+1}$而言，$x,y$可能不是最优决策。
- 那么有$f_{i,j}+f_{i+1,j+1}\le f_{i,x}+f_{x+1,j}+w_{i,j}+f_{i+1,y}+f_{y+1,j+1}+w_{i+1,j+1}$
- 由于$w$满足四边形不等式，即$w_{i,j+1}+w_{i+1,j}\ge w_{i,j}+w_{i+1,j+1}$。
- 根据假设，有:$f_{i+1,x}+f_{i,y}\ge f_{i,x}+f_{i+1,y}$
- 结合这两个不等式，再比较上述二式，得到:$f_{i+1,j}+f_{i,j+1}\ge f_{i,j}+f_{i+1,j+1}$
证毕。
二维决策单调性
简记$p_{i,j}$为令$f_{i,j}$取到最小值的$k$值，那么$p_{i,j-1}\le p_{i,j}\le p_{i+1,j}$
证明:
- 记$p=p_{i,j}$，那么对于$\forall i<k\le p$，因为$f$满足四边形不等式，则有
$f_{i,p}+f_{i+1,k}\ge f_{i,k}+f_{i+1,p}$
$f_{i+1,k}-f_{i+1,p}\ge f_{i,k}-f_{i,p}$
- 因为$p$的最优性，那么$f_{i,k}+f_{k+1,j}\ge f_{i,p}+f_{p+1,j}$
- 因此$(f_{i+1,k}+f_{k+1,j}+w_{i+1,j})-(f_{i+1,p}+f_{p+1,j}+w_{i+1,j})=f_{i+1,k}+f_{k+1,j}-f_{i+1,p}-f_{p+1,j}\ge f_{i,k}-f_{i,p}+f_{k+1,j}-f_{p+1,j}\ge 0$
因此$f_{i+1,k}+f_{k+1,j}\ge f_{i+1,p}+f_{p+1,j}$
所以对于$f_{i+1,j}$来说，$p$优于任何的$k\le p$。因此$p_{i+1,j}\ge p_{i,j}$
同理，$p_{i,j-1}\le p_{i,j}$
证毕。
0 条评论