首页 > 代码库 > ZOJ 3790 Consecutive Blocks

ZOJ 3790 Consecutive Blocks

给定一个数字序列,最多可以删除k个数字(就相当于链表删除操作,删除后左右序列连接),问,和值最大是多少,题目所指的和值为 相等的连续数字的和

比如 1 1 2 1 1 1,原本的和值为3(三个连续的1),如果允许删除一次,则我把2删除,则和值为5(5个连续的1)

首先,最后能造成结果最大的,只有一个数字,所以我的k次操作必定是用于将其中某个数字中间的障碍清除,使其最大,

于是我先离散化,把连续数字都缩成一个块,最后枚举每个数字,用一个p q指针维护头尾,代表当前p和q之间的块为最大值,然后如果条件允许(k够用)就q++,否则p++,走一遍下来即可

其他很多人貌似用的是枚举起点,二分终点,也挺不错的,我因为比赛的时候用的是这个,感觉也挺不错的,而且对某些数据,应该还会快过他们二分的

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <vector>using namespace std;const int N = 100000+10;int X[N];int A[N],d[N];int n,k,m,cnt;struct node{    int c,l,r,val;}block[N];vector<int>  v2[N];vector<int>  v4[N];vector<int>  v3[N];int main(){    while (scanf("%d%d",&n,&k)!=EOF)    {        for (int i=1;i<=n;i++){            scanf("%d",&A[i]);            X[i]=A[i];            d[i]=1;            v2[i].clear();            v3[i].clear();            v4[i].clear();        }        sort(X+1,X+1+n);        m=1;        for (int i=2;i<=n;i++){            if (X[i]!=X[i-1]) X[++m]=X[i];        }        for (int i=1;i<=n;i++){            int pos=lower_bound(X+1,X+1+m,A[i])-X;            A[i]=pos;        }        for (int i=2;i<=n;i++){            if (A[i]==A[i-1]) d[i]=d[i-1]+1;        }        cnt=0;        int ans=0;        for (int i=1;i<=n;i++){            ans=max(ans,d[i]);            if (i==n || d[i+1]==1){                block[++cnt]=(node){A[i],i-d[i]+1,i,d[i]};                int r2=v2[A[i]].size();                int r3=v3[A[i]].size();                if (r3==0){                    v3[A[i]].push_back(0);                    v4[A[i]].push_back(block[cnt].val);                }                else{                    v4[A[i]].push_back(v4[A[i]][r3-1]+block[cnt].val);                    int pre=v2[A[i]][r2-1];                    v3[A[i]].push_back(v3[A[i]][r3-1]+block[cnt].l-block[pre].r-1);                }                v2[A[i]].push_back(cnt);            }        }        for (int i=1;i<=m;i++){            //cout<<"Test"<<" "<<i<<endl;            int sum=0;            int p=0,q=0,sz=v2[i].size();            if (sz==1) continue;            sum+=v4[i][0];            q++;            for (q;q<sz;){                node pre=block[v2[i][p]];                int cost=v3[i][q]-v3[i][p];                if (cost<=k){                    sum=max(sum,v4[i][q]-v4[i][p]+pre.val);//                    cout<<v4[i][q]<<" "<<v4[i][p]<<" "<<pre.val<<endl;//                    cout<<v4[i][q]-v4[i][p]+pre.val<<endl;                    q++;                }                else{                    p++;                }//                cout<<"pq "<<p<<" "<<q<<endl;//                cout<<"cost "<<cost<<endl;//                cout<<"sum "<<sum<<endl;            }            ans=max(ans,sum);        }        printf("%d\n",ans);    }    return 0;}