建模+线性dp——cf1201D

桃扇骨 2023-10-11 09:09 51阅读 0赞

这类题目要首先把模型建立起来，挑选一个好的状态能让dp方程简化很多

/* dp[i][0]表示从右到左，最后停在左端 dp[i][1]表示从左到右，最后停在右端 dp[i+1][0]=min(dis(Lpre->Ri+1)+dp[pre][0], dis(Rpre->Ri+1)+dp[pre][1]) + Ri+1-Li+1 dp[i+1][1]=min(dis(Lpre->Li+1)+dp[pre][0], dis(Rpre->Li+1)+dp[pre][1]) + Ri+1-Li+1; */
    #include<bits/stdc++.h>
    using namespace std;
    #define ll long long 
    #define N 200005
    #define INF 0x3f3f3f3f3f3f3f3f
    
    ll n,m,k,q,b[N],L[N],R[N],dp[N][2];
    
    long long dis(ll pos1,ll pos2){
        //pos1->pos2的代价
        if(pos1>pos2)swap(pos1,pos2);
        int t=lower_bound(b+1,b+1+q,pos1)-b;
        if(t!=q+1 && b[t]<=pos2)return pos2-pos1;//有夹在中间的 
        
        ll res=INF;
        //找pos1左边的
        if(t!=1){
            t--;
            res=min(res,2*(pos1-b[t])+pos2-pos1);
        }
        t=lower_bound(b+1,b+1+q,pos2)-b;
        if(t!=q+1)
            res=min(res,2*(b[t]-pos2)+pos2-pos1);
        return res;
    }
    
    int main(){
        memset(L,0x3f,sizeof L);
        memset(R,0,sizeof R);
        L[1]=R[1]=1;
        cin>>n>>m>>k>>q;
        for(int i=1;i<=k;i++){
            ll r,c;cin>>r>>c;
            L[r]=min(L[r],c);
            R[r]=max(R[r],c);
        }
        for(int i=1;i<=q;i++)cin>>b[i];
        sort(b+1,b+1+q);
        
        memset(dp,0x3f,sizeof dp);
        //预处理第一行
        if(R[1]!=1)dp[1][1]=R[1]-1;//如果第一行有(1,1)之外的点，则必须停在右端 
        else dp[1][1]=dp[1][0]=0; //点在(1,1)或没有点，则停在左右端的代价都是0 
        
        int pre=1; 
        for(int i=2;i<=n;i++)if(R[i]){
            dp[i][0]=min(dis(L[pre],R[i])+dp[pre][0] , dis(R[pre],R[i])+dp[pre][1])+R[i]-L[i];//右到左 
            dp[i][1]=min(dis(L[pre],L[i])+dp[pre][0] , dis(R[pre],L[i])+dp[pre][1])+R[i]-L[i];//左到右 
            pre=i;
        }
        
        cout<<min(dp[pre][0],dp[pre][1])+pre-1<<'\n';
    }

转载于:https://www.cnblogs.com/zsben991126/p/11516850.html