ftiasch 18岁生日的时候,lqp18_31给她看了一个神奇的序列 A1, A2, …, AN. 她被允许选择不超过 M 个连续的部分作为自己的生日礼物。
自然地,ftiasch想要知道选择元素之和的最大值。你能帮助她吗?
首先,先把连续的正数负数合并,排列成正负交错的数列
此时如果有小于等于M个正数数列,那么答案就是他们的和
否则,我们维护每一项的绝对值按照从小到大排列的顺序
每次取出绝对值最小的
如果该数为正项,那么从ans中减去该数,同时与两边的负数合并后装入堆中。
删掉表示不选该数,与两边合并,使得3段变1段,同时原来两边之和的绝对值减小,保证之后的合并使最优的。
如果该数为负数,如果该数不是最左或者最右边,那么与两边的数直接合并,并且在ans中减掉该数的绝对值。
两种情况都可以使原来选的数的个数减1,并且损失的代价最小。
如果是负数并且在两边,无法合并直接丢掉,并且无法使选的数减小。
小技巧:
删除堆中指定元素
- 手写堆,把该元素改成正无穷或者负无穷,然后pushup或者pushdown,之后要么在最上面要么在最下面,在最下面就不管,在最上面就pop掉。
2.新开个堆,把删除的元素装入。每次检查两个堆堆顶如果相同,同时pop掉。
CODE:
#include<bits/stdc++.h>
const int N = 1e5+1e3;
int a[N],cnt,n,pre[N],m,nxt[N],sum,ans;
struct heap{
int v,pos;
bool operator < (const heap m) const{
if(v!=m.v)return v>m.v;
return pos>m.pos;
}
bool operator == (const heap m) const{
return v==m.v&&pos==m.pos;
}
};
std::priority_queue<heap> q,d;
void up(){while(!q.empty()&&!d.empty()&&q.top()==d.top())q.pop(),d.pop();}
void del(heap x){d.push(x);
up();}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i){
int x;
scanf("%d",&x);
if((a[cnt]<=0&&x<=0)||(a[cnt]>=0&&x>=0)) a[cnt]+=x;
else a[++cnt]=x;
}
n=cnt;
for(int i=1;i<=n;++i){
pre[i]=i-1,nxt[i]=i+1;
q.push((heap){abs(a[i]),i});
if(a[i]>0) ans+=a[i],sum++;
}
pre[1]=nxt[n]=0;int T=0;
// while(!q.empty()){++T;
// heap x=q.top();q.pop();
// printf("%d %d %d\n",T,x.pos,x.v);
// if(x.v==1000) break;
// }
while(sum>m){
heap x=q.top();
del(x);
--sum;
if(!pre[x.pos]){
if(a[x.pos]>0){
ans-=a[x.pos];pre[nxt[x.pos]]=0;
//del((heap){abs(a[nxt[x.pos]]),x.pos});
}
else{
pre[nxt[x.pos]]=0;sum++;
}
}
else if(!nxt[x.pos]){
if(a[x.pos]>0){
ans-=a[x.pos];nxt[pre[x.pos]]=0;
//del((heap){abs(a[pre[x.pos]]),x.pos});
}
else{
nxt[pre[x.pos]]=0;sum++;
}
}
else {
ans-=x.v;
a[x.pos]+=a[nxt[x.pos]]+a[pre[x.pos]];
del((heap){abs(a[nxt[x.pos]]),nxt[x.pos]});
del((heap){abs(a[pre[x.pos]]),pre[x.pos]});
nxt[pre[pre[x.pos]]]=x.pos;pre[x.pos]=pre[pre[x.pos]];
pre[nxt[nxt[x.pos]]]=x.pos;nxt[x.pos]=nxt[nxt[x.pos]];
q.push((heap){abs(a[x.pos]),x.pos});
}
}
printf("%d\n",ans);
return 0;
}
0 条评论