决策单调性优化胡扯

四边形不等式

设二元函数$w(i,j)$

对于$a<=b<=c<=d$

若$w(a,d)+w(b,c)>=w(a,c)+w(b,d)$

则函数$w$满足四边形不等式

引理1

若二元函数$w(i,j)$满足对于$i<j$

则说明该函数满足四边形不等式

证明

对于$a<c$

对于$a+1<c$

两式相加得：

$w(a,c+1)+w(a+2,c)>=w(a,c)+w(a+2,c+1)$

以此类推直至引理得证

引理2

若对于方程$f[i]=min_{0<=j<i} (f[j]+val(j,i))$

若函数val 满足四边形不等式 则其具有决策单调性（决策点单调不减）

证明

设p[i]表示i的决策点

根据p[i]的最优性 有

$f[p[i]]+val(p[i],i)<=f[j]+val(j,i) 对于所有j属于[0,p[i]-1]$

对于所有$i’属于[i+1,N]$ 有

$val(j,i’)+val(p[i],i)>=val(j,i)+val(p[i],i’)$

$val(p[i],i’)-val(p[i],i)<=val(j,i’)-val(j,i)$

与一式相加

$f[p[i]]+val(p[i],i’)<=f[j]+val(j,i’)$

这说明 以p[i]作为决策比以j<p[i]好 也就是决策单调性

决策单调性优化实现

考虑维护p数组 每当我们求出一个i时 最终我们将找到i在p中的一个位置 从此之后p都填i 显然可以二分

建立一个三元队列 $(j,l,r)$ j为决策 l为左端点 r为右端点

从队尾开始检查 直到某个元素r更优 l更劣 在其中二分即可

另外 由证明显然得 若方程为max 则四边形不等式反向即可

二维情况

多见于区间dp

引理3

对于dp方程$f[i,j]=min_{i<=k<j}(f[i,k]+f[k+1,j]+w(i,j))$

若以下两条件成立：

1 w满足四边形不等式

2 对于任意a<=b<=c<=d 有w(a,d)>w(b,c)

则f满足四边形不等式

证明

当j-i=1时 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,i+2]=f[i,i+1]+f[i+2,i+2]+w(i,i+2)=w(i,i+1)+w(i,i+2)>=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,i+2]=f[i,i]+f[i+1,i+2]+w(i,i+2)=w(i+1,i+2)+w(i,i+2)>=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]

于是j-i=1 四边形不等是对f[i,j]成立

用数学归纳法证明即可

引理4

在状态转移方程$f[i,j]=min_{i<=k<j}{f[i,k]+f[k+1,i]+w(i,j)}$中

如果f满足四边形不等式 则p[i,j-1]<=p[i,j]<=p[i+1,j]

证明

类似引理2 略（

优化实现

保存p数组 按照引理4枚举即可