四边形不等式和决策单调性

· · 算法·理论

四边形不等式的定义

当对于a,b,c,d满足a\le b\le c\le d时，

w(a,d)+w(b,c)\ge w(a,c)+w(b,d)

称w满足四边形不等式。

第一类DP优化

f_i=\min_{j<i}\{f_j+w(j+i)\}

决策单调性

指的是f_i的决策点j满足单调性，

相当于j 随着 i 的增大而增

当新加入的i是新的决策点时，相当于:

f_{i'}+w_{i,i'}<f_{i'}+w_{j,i'}

因而后面的连续一段的决策点都为i

因此新加入元素(pos,n,i),原尾部元素r变为pos-1

算法实现

单调队列 维护决策集合P

单调队列中储存了一个三元组(l,r,j),表示,从l到r的最优决策点都为j

对于每一个i\in [1,n]，执行下面操作：

  1. 删除无效队头：当队头为(l,r,j)，若r\le i-1，说明当前对头对于答案无效，弹出对头。否则将l设为i
  2. 取出队头的最优决策点，更新当前f_i

  3. 插入新元素:i

    (1) 取出当前队尾(l,r,j)

    (2) 若f[l]+w(i,l)\le f[j]+w(j,l)，则删除队尾，回到(1)操作。

    (3) 用二分在[l,r]中找出pos,使pos前此决策优，pos后(包含pos) i更优，将(l,r,j)修改为(l,pos-1,j)

    (4) 将 (pos,n,i) 放入队尾

时间复杂度O(n\ log\ n)。

代码实现

int n;
int l,r,q[N];
int L[N],R[N];
int w(int x,int y);
void solve(){//写法一，加入f[0]
    l=1,r=1,q[1]=0;
    L[0]=1,R[0]=n;
    for(int i=1;i<=n;i++){
        while(l<=r && R[q[l]]<i) //弹出队首无用项
            l++;
        f[i]=w(q[l],i);
        while(l<=r && w(i,L[q[r]])<=w(q[r],L[q[r]]))//弹出队尾无用项 
            r--;
        int ll=L[q[r]],rr=n+1;
        while(ll<rr){//二分获得pos
            int mid=ll+rr>>1;
            if(w(i,mid)<=w(q[r],mid)) rr=mid;
            else ll=mid+1;
        }
        if(ll>n) continue;
        R[q[r]]=ll-1;
        q[++r]=i;
        L[i]=ll,R[i]=n;
    }
}

void solve(){//写法二，不加入f[0]
    l=1,r=0;
    for(int i=1;i<=n;i++){
        int ans=n+1;
        L[q[r]]=max(L[q[r]],i);
        while(l<=r && w(i,L[q[r]])>=w(q[r],L[q[r]]))//弹出队尾无用项 
            r--;
        if(l<=r && w(i,R[q[r]])>=w(q[r],R[q[r]])){
            ans=R[q[r]]+1;
            int ll=L[q[r]],rr=R[q[r]];
            while(ll<=rr){//二分获得pos
                int mid=ll+rr>>1;
                if(w(i,mid)>=w(q[r],mid)) ans=mid,rr=mid-1;
                else ll=mid+1;
            }
            R[q[r]]=ans-1;
        }
        if(l>r) q[++r]=i,L[i]=i,R[i]=n;
        if(ans!=n+1) q[++r]=i,L[i]=ans,R[i]=n;
        while(l<=r && R[q[l]]<i) //弹出队首无用项
            l++;
        L[q[l]]=i;
        f[i]=max(f[i],w(q[l],i));
    }
}

分治

假设已知[l,r]的最优决策在[L,R]上。

定义mid=l+r>>1,设dp[mid]的最优决策为p,根据决策单调性,可知[l,mid−1]的最优决策在[L,p]内,[mid+1,r]的最优决策在[p,R]内。

于是将问题分割成了同类型的规模更小的问题，便可递归分治。

时间复杂度O(n\ logn)

代码实现

int w(int j,int i);
void DP(int l,int r,int ll,int rr) {
    int mid=l+r>>1,k=ll;
    for (int j=ll;j<=min(rr,mid-1);j++)//寻找当前决策点
        if (w(j,mid)<w(k,mid)) k=j;
    f[mid]=w(k,mid);
    if(l<mid) DP(l,mid-1,ll,k);
    if(r>mid) DP(mid+1,r,k,rr);
}

第二类DP优化

f_{i,j}=\min_{i\le k \le j}\{f_{i,k}+f_{k+1,j}\}+w_{i,j}

决策单调性

当 i<i'\le j < j',满足：

P_{i，j'}\le P_{i',j}$ 且 $P_{i,j-1}\le P_{i,j}\le P_{i+1,j}

代码实现

int w(int j,int i);
for(int i=1;i<=n;i++) f[i][i]=f[i+1][i]=f[i][i-1]=0,p[i][i]=i;
for(int len=2;len<=n;len++){
    for(int i=1;i+len-1<=n;i++){
        int j=i+len-1;
        for(int k=p[i][j-1];k<=p[i+1][j];k++){
            if(f[i][j]>f[i][k-1]+f[k+1][j]+w(i,j)){
                f[i][j]=f[i][k-1]+f[k+1][j]+w(i,j);
                p[i][j]=k;
            }
        }
    }
}
cout<<f[1][n]<<'\n';