四边形不等式

wfycsw · 2022-10-31 14:44:27 · 个人记录

四边形不等式

定义：若w(l,r)，满足当l1\le l2\le r1\le r2时，满足w(l1,r1)+w(l2,r2)\le w(l1,r2)+w(l2,r1)，（简记为交叉大于包含） 则称w(l,r)满足四边形不等式。

1D1D优化

个人理解：对于一个递推式形如:dp_i=max(dp_i,dp_j+w(i,j))的转移，设k=j_d为每次转移的最优决策点，若其有k_1 \le k_2 \le k_3 \le ....k_n,即k非降。那么就说这个dp具有决策单调性。

满足条件：w(i,j)满足四边形不等式。（当然如果不会证四边形不等式，也可以打表验证，之后猜完后再挂个对拍）。

至于为什么，请看OI Wiki。

通过决策单调性优化的实现主要有两种方法：

方法一：递归求解

直接拿Lightning Conductor来说。

#include<bits/stdc++.h>
#define RI register int
#define ll long long
#define err puts("asd")
#define ed puts("end")
#define db long double
#define mk make_pair
//#define int long long
using namespace std;
inline ll read(){
    ll s=0;register char c=getchar();bool f=0;
    while(c<'0'||c>'9'){if(c=='-') f=1;c=getchar();}
    while(c>='0'&&c<='9') s=(s<<1)+(s<<3)+c-48,c=getchar();
    return f?-s:s;
}   
const int N=5e5+5;
int a[N],ans[N],n;
inline int calc(int i,int j){return ceil(sqrt(abs(i-j)))+a[j];}
inline void solve(int l,int r,int kl,int kr){
    /*
    l和r表示但前的求解区间，kl和kr表示当前区间最优转移点的可能取值

    先暴力求出中间mid的答案和最优转移点k。
    然后分左右区间递归
    */
    RI mid=l+r>>1,k=0,maxl=-1,p;
    for(RI i=kl,d=min(kr,mid);i<=d;++i){
        p=calc(mid,i);//择优
        if(p>maxl) maxl=p,k=i;
    }
    ans[mid]=max(ans[mid],maxl);
    if(mid!=l) solve(l,mid-1,kl,k);
    if(mid!=r) solve(mid+1,r,k,kr);
}
inline void solve1(int l,int r,int kl,int kr){
    //反过来搞一遍
    RI mid=l+r>>1,k=0,maxl=-1,p;
    for(RI i=kr,d=max(mid,kl);i>=d;--i){
        p=calc(mid,i);
        if(p>maxl) maxl=p,k=i;
    }
    ans[mid]=max(ans[mid],maxl);
    if(mid!=l) solve1(l,mid-1,kl,k);
    if(mid!=r) solve1(mid+1,r,k,kr);
}
signed main(){
    freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    n=read();
    for(RI i=1;i<=n;++i) a[i]=read(),ans[i]=-2e9;
    solve(1,n,1,n);
    solve1(1,n,1,n);
    for(RI i=1;i<=n;++i)
        printf("%d\n",ans[i]-a[i]);
    return 0;
}

方法二：决策二分栈

这种方法主要思路类似于刷表法：直接维护每个决策点更新哪些点的答案是最优的。对于每个决策点，用一个结构体记录他的最优区间l,r和id，表示在[l,r]这个区间的点用这个决策点来更新最优。

于是，每次就可以O(1)出答案。

那如何更新呢？

具体的更新细节，还是用上面那道题细讲：

#include<bits/stdc++.h>
#define RI register int
#define ll long long
#define err puts("asd")
#define ed puts("end")
#define db long double
#define mk make_pair
//#define int long long
using namespace std;
inline ll read(){
    ll s=0;register char c=getchar();bool f=0;
    while(c<'0'||c>'9'){if(c=='-') f=1;c=getchar();}
    while(c>='0'&&c<='9') s=(s<<1)+(s<<3)+c-48,c=getchar();
    return f?-s:s;
}   
const int N=5e5+5;
int a[N],ans[N],n,t,w;
struct wu{
    int l,r,x;//这里的x就是id
}d[N];
inline double calc(int i,int j){return sqrt(abs(i-j))+a[j];}
inline void binary(int i){
    RI x=d[w].x,l=d[w].l,r=d[w].r,mid,ans=r+1;
    while(l<=r){
        mid=l+r>>1;
        if(calc(mid,i)>=calc(mid,x)) ans=mid,r=mid-1;//如果i比x强就往左挤
        else l=mid+1;//不然往后退
    }
    d[w].r=ans-1;//划分界限
    if(ans<=n) d[++w]=(wu){ans,n,i};
}
inline void binary1(int i){
    RI x=d[w].x,l=d[w].l,r=d[w].r,mid,ans=l-1;
    while(l<=r){
        mid=l+r>>1;
        if(calc(mid,i)>=calc(mid,x)) ans=mid,l=mid+1;
        else r=mid-1;
    }
    d[w].l=ans+1;
    if(ans>0) d[++w]=(wu){1,ans,i};
}
signed main(){
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    n=read();
    RI x,y,z,q,p;
    for(RI i=1;i<=n;++i) a[i]=read(),ans[i]=-2e9;
    /*
    因为每个决策点的更新的最优点一定是连续的，即构成一个区间，于是便可以维护一个类似于队列的栈（我也不明白为什么不是队列），
    */
    t=1;d[w=1]=(wu){1,n,1};ans[1]=(int)ceil(calc(1,1));
    for(RI i=2;i<=n;++i){
        while(t<=w&&d[t].r<i) ++t;//对于已经完全挨不到i的点直接弹出，因为肯定也挨不到后面
        d[t].l=i;//当前需要转移的最左端的最优点变为i，千万注意不要漏
        while(t<=w&&calc(d[w].l,d[w].x)<=calc(d[w].l,i)) --w;//因为满足单调性，做一连转移最左段的点都不如i,那要他有何用，直接丢掉。
        if(t>w) d[++w]=(wu){i,n,i};//假如没有点了直接加在队尾
        else binary(i);//不然二分查找界限
        ans[i]=max(ans[i],(int)ceil(calc(i,d[t].x)));//更新答案
    }

    t=1;d[w=1]=(wu){1,n,n};ans[n]=max(ans[n],(int)ceil(calc(n,n)));
    for(RI i=n-1;i>0;--i){
        while(t<=w&&d[t].l>i) ++t;
        d[t].r=i;
        while(t<=w&&calc(d[w].r,d[w].x)<=calc(d[w].r,i)) --w;
        if(t>w) d[++w]=(wu){1,i,i};
        else binary1(i);
        ans[i]=max(ans[i],(int)ceil(calc(i,d[t].x))); 
    }
    for(RI i=1;i<=n;++i)
        printf("%d\n",ans[i]-a[i]);
    return 0;
}

总

关于这两种方法，其中递归求解常数较小，但是不好维护dp的转移，只能维护分层的dp;而二分栈则一般可以维护1D1D的DP。

2D1D优化

对于2D1D的dp转移,形如:dp_{i,j}=dp_{i,k}+dp_{k+1,j}+w(i,j)，其中k为决策点，记为m_{i,j}=k，若其满足w(l,r)具有四边形不等式，且具有区间包含单调性（即对于任意l1\le l2\le r2\le r1,有w(l2,r2)\le w(l1,r1)，则有m_{i,j-1} \le m_{i,j} \le m_{i+1,j}。

证明：请看OI Wiki。

邮局

#include<bits/stdc++.h>
#define err puts("asd")
#define rre puts("dsa")
#define ll long long
#define P(x) printf("asd %d\n",x)
#define no puts("NO")
#define yes puts("YES")
#define RI register int
#define rand (rand()*rand()+rand())%1000000000
//#define int long long 
using namespace std;
inline int read(){
    RI s=0;register char c=getchar();bool f=0;
    while(c<'0'||c>'9'){if(c=='-') f=1;c=getchar();}
    while(c>='0'&&c<='9') s=(s<<1)+(s<<3)+c-48,c=getchar();
    return f?-s:s;
}
const int M=305;
const int N=3e3+5;
int f[N][M],dis[N][N],m[N][M],a[N],n,p;
inline void init(){
    for(RI i=1;i<=n;++i)//预处理
        for(RI j=i+1;j<=n;++j)
            dis[i][j]=dis[i][j-1]+a[j]-a[i+j>>1];
}
signed main(){
    //freopen("1.in","r",stdin);
    n=read(),p=read();
    for(RI i=1;i<=n;++i) a[i]=read();
    init();
    memset(f,127/3,sizeof f);
    f[0][0]=0;
    //sort(a+1,a+n+1);
    for(RI j=1;j<=p;++j){
        m[n+1][j]=n;
        for(RI i=n;i>0;--i){//因为要用到m[i+1][j]，所以倒序求解。
            f[i][j]=1e9;
            //RI L=m[i][j-1]?m[i][j-1]:j;
            //RI R=m[i+1][j]?m[i+1][j]:i;
            for(RI k=m[i][j-1];k<=m[i+1][j];++k){
                RI d=f[k][j-1]+dis[k+1][i];
                //acout<<k+1<<' '<<i<<' '<<dis[k+1][i]<<endl;
                if(f[i][j]>d) f[i][j]=d,m[i][j]=k;  
            }
        }
    }
    cout<<f[n][p];
    return 0;
}