以下博客在一派胡言,大家当我口胡就行
满足决策单调性,因为满足四边形不等式所以满足决策单调性
四边形不等式:
a<b<c<d
val(a,d)+val(b,c)>=val(a,b)+val(c,d)
拓展若val(a,b+1)+val(a+1,b)>=val(a,b)+val(a+1,b+1)则满足四边形不等式
定理形如$f[i]=min(f[j]+val(j,i))$dp式子,若$val(j,i)$满足四边形不等式则满足决策单调性
注意这里是min,,,,max可能不成立
证明:
设$p[i]$为$i$转移点最优决策,$jin[1,p[i]-1]$
有$f[p[i]]+val(p[i],i)<=f[j]+val(j,i)$
设$i_2in[i+1,n]$
$val$满足四边形不等式
$j<p[i]<i<i_2$
故$val(j,i_2)+val(p[i],i)>=val(j,p[i])+val(i,i_2)$
所以$val(j,p[i])-val(p[i],i)<=val(j,i_2)-val(i,i_2)$
与上面式子相加$f[p[i]]+val(p[i],i_2)<=f[j]+val(j,i_2)$
表示所有<=p[i]转移点都不优,换句话说就是 决策点单调递增,p[i+1]>=p[i],p[i+2]>=p[i+1]
二维$dp$证明略
下面证明二维$dp$,若满足四边形不等式设$juec[i][j]$为$f[i][j]$转移点,则$juec[i][j-1]<=juec[i][j]<=juec[i+1][j]$
$juec[i][j]>=juec[i][j-1]$,设$p=juec[i][j-1]$
有$f[i][p]+f[p][j]+val(i,j)<=f[i][k]+f[k][j]+val(i,j)$
于是$!@#%!@!^&*$什么,这个题不是四边形不等式??????????????????????
我们假装是四边形不等式,套用
val(a,b+1)+val(a+1,b)>=val(a,b)+val(a+1,b+1)
于是满足决策单调
于是是$n^2$了
好傻逼