首页 > 代码库 > 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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。