分治维护dp——19南昌网络赛C/cf750E

桃扇骨 2023-10-11 07:49 10阅读 0赞

南昌网络赛，是cf的原题

第一次做到这种题，所以认真想了下，每次给一个询问\[L，R\],要求出这个区间里有2017子序列，但是不能有2016子序列需要删掉的最少元素个数

首先如果我们之询问一小段区间\[L,R\]那么显然有一个简单的三维dp可以做，状态0|1|2|3|4表示关键字一个也没有，有2，有21，有201，有2017的情况，dp\[i\]\[j\]表示从状态i转移到状态j最小需要删除的字符

那么显然当s\[i\]=6时，有dp\[3\]\[3\]=1,dp\[4\]\[4\]=1

可以发现，这种状态是很好合并的,对于区间\[l,mid\]和区间\[mid+1,r\]，设前一半的状态是dp1,后一半的状态是dp2,,两个区间合起来的状态是dp\[l\]\[r\]，那么就有dp1\[l\]\[k\]+dp2\[k\]\[r\]=dp\[l\]\[r\]

所以我们可以直接用分治来求任意一个区间的所有状态复杂度是O（125/6nlogn）因为时间给的多，所以足够快

#include<bits/stdc++.h>
    using namespace std;
    #define N 200005
    #define INF 0x3f3f3f3f
    char s[N];
    int n,q;
    
    void reserve(int l,int r){
        int i=l,j=r;
        while(i<j){
            swap(s[i],s[j]);
            ++i,--j;
        }
    }
    
    //状态0表示什么都没有，状态1表示2，状态2表示20，状态3表示201，状态4表示2019,dp[i][j]表示从i->j的代价 
    //因为每段相邻的段状态具有可合并性，想到用线段树分治来维护合并信息，线段树[l,r]维护[l,r]所有状态的代价，合并时类似n^3的区间dp转移 
    struct Node{
        int dp[5][5];
        Node(){
            memset(dp,0x3f,sizeof dp);
        }
    }seg[N<<2];
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1 
    Node merge(Node a,Node b){
        Node res;
        for(int l=0;l<5;l++)
            for(int r=0;r<5;r++)
                for(int k=0;k<5;k++)
                    res.dp[l][r]=min(res.dp[l][r],a.dp[l][k]+b.dp[k][r]);
        return res;
    } 
    void build(int l,int r,int rt){
        if(l==r){
            for(int i=0;i<5;i++)
                seg[rt].dp[i][i]=0;
            if(s[l]=='2'){
                seg[rt].dp[0][0]=1;seg[rt].dp[0][1]=0;
            }else if(s[l]=='0'){
                seg[rt].dp[1][1]=1;seg[rt].dp[1][2]=0;
            }else if(s[l]=='1'){
                seg[rt].dp[2][2]=1;seg[rt].dp[2][3]=0;
            }else if(s[l]=='9'){
                seg[rt].dp[3][3]=1;seg[rt].dp[3][4]=0;
            }else if(s[l]=='8'){
                seg[rt].dp[3][3]=1;seg[rt].dp[4][4]=1;
            }
            return;
        }
        int m=l+r>>1;
        build(lson),build(rson);
        seg[rt]=merge(seg[rt<<1],seg[rt<<1|1]);
    }
    Node query(int L,int R,int l,int r,int rt){
        if(L<=l && R>=r)return seg[rt];
        int m=l+r>>1;
        Node res;
        for(int i=0;i<5;i++)res.dp[i][i]=0;
        if(L<=m)res=merge(res,query(L,R,lson));
        if(R>m)res=merge(res,query(L,R,rson));
        return res;
    }
    
    
    int main(){
        cin>>n>>q;
        scanf("%s",s+1);
        reserve(1,n); 
        build(1,n,1);
        while(q--){
            int L,R;
            scanf("%d%d",&L,&R);
            L=n-L+1;R=n-R+1;
            Node res=query(R,L,1,n,1);
            if(res.dp[0][4]==INF)
                puts("-1");
            else cout<<res.dp[0][4]<<endl;
        }
    }

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