初探四边形不等式

对于$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$),如果下面两个条件成立:

  1. $w$满足四边形不等式
  2. 对于任意的$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}$

证毕。