首页 > 代码库 > ZOJ 3790 Consecutive Blocks

ZOJ 3790 Consecutive Blocks

2024-07-16 18:46:44   224人阅读

给定一个数字序列，最多可以删除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;}

　　


联系
我们