四边形不等式
定理1:
设w(x,y)为定义在整数集合上的二元函数,若存在任意整数a,b,c,d(a<=b<=c<=d),并且w(a,d)+w(b,c)>=w(a,c)+w(b,d)都成立,则w(x,y)满足四边形不等式。
定理2:
设w(x,y)为定义在整数集合上的二元函数,若存在任意整数a,b(a<b),并且w(a,b+1)+w(a+1,b)>=w(a,b)+w(a+1,b+1)都成立,则w(x,y)也满足四边形不等式。
用数学归纳法证明即可。
决策单调性
假设转移方程为dp[i]=min(dp[j]+v(j,i)),v(j,i)为状态j到状态i的转移代价。设p[i]为转移到i状态最优的j，如果p[i]在定义域上单调不下降则称转移方程具有决策单调性。
定理:
若在上述转移方程中v(j,i)满足四边形不等式,则转移方程满足决策单调性。
证明:
观察式③可以发现,当j<p[i]时,以p[i]作为dp[i`]的决策比j要好,那么以此可以得出p[i`]>=p[i],既转移方程满足决策单调性。
应用
如何通过决策单调性将o(n^2)的复杂度降到o(nlogn)呢？
关键在于如何维护p数组，首先再回顾一下p数组的意义:p[i]是dp[i]的最优决策,既dp[i]=dp[p[i]]+v(p[i],i)最优。并且p数组单调不下降，根据单调不下降的性质可以维护一个单调队列，队列元素为(x,l,r)三元组表示p[l-r]=x。每次添加一个新决策i都要与之前的决策比较，删除p[1~i-1]的决策，维护它最优决策的性质。
总结一下过程,对于每个i，执行下列操作:
1.设队首为(j,l,r),若r<i,则删除队首,保证队首的决策对应dp[i]。然后再令l++(举例:当队首为(1,2,5)，而i==2时,删除p[2],因为对i+1来说p[1~i]没有意义)。
2.计算dp[i]=dp[j]+v(j,i)
3.插入新决策i(具体过程见板子)。
q[].x=;q[].l=;q[].r=n;t=h=;
for(int i=;i<=n;i++){
while(h<=t&&q[h].r<i) h++;//h表示队首，删除队首
q[h].l++;
dp[i]=dp[q[h].x]+val(i,q[h].x);
int pos=1e9;
while(h<=t&&dp[i]+val(q[t].l,i)<=dp[q[t].x]+val(q[t].l,q[t].x))
pos=q[t].l,t--;//当队尾决策都不如决策i好时，删去队尾
if(h<=t&&dp[q[t].x]+val(q[t].r,q[t].x)>dp[i]+val(q[t].r,i)){
int l=q[t].l,r=q[t].r,mid,p1=q[t].r+;
while(l<=r){//二分求出以i为最优决策的位置p1,p1之后i决策更优
mid=l+r>>;
if(dp[q[t].x]+val(mid,q[t].x)>=dp[i]+val(mid,i))
p1=mid,r=mid-;
else
l=mid+;
}
q[t].r=p1-;pos=p1;
}
if(pos<=n){
++t;q[t].l=pos;q[t].r=n;q[t].x=i;
}
}
板子