https://www.lydsy.com/JudgeOnline/problem.php?id=2288
ftiasch 18岁生日的时候，lqp18_31给她看了一个神奇的序列 A1, A2, ..., AN. 她被允许选择不超过 M 个连续的部分作为自己的生日礼物。
自然地，ftiasch想要知道选择元素之和的最大值。你能帮助她吗？
这题很像BZOJ1150：[APIO/CTSC2007]数据备份，但如果没有做过的话其实也不要紧。
参考：https://www.cnblogs.com/zyfzyf/p/4114774.html感觉hzwer博客不是很好懂。
我们首先将相同符号的点缩起来，去掉首末的负结点，然后思考。
如果当前的正数个数<=m显然就求一遍和即可。
如果>m的话就有两种选择了：
1.忍痛割爱弃掉一个正数。
2.选择一个负数，将两旁正数连同负数一起缩进来。
我们发现这两个操作都是在原ans的基础上支付我们选择的点代价的，因此我们支付的代价越少越好，故我们将点权的abs放入小根堆里，每次拿出来之后和两边的点缩起来即可。
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
#define fi first
#define se second
const int N=1e5+;
const int INF=1e9+;
inline int read(){
int X=,w=;char ch=;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();
return w?-X:X;
}
struct node{
int x,y;
node(int xx=,int yy=){
x=xx;y=yy;
}
bool operator <(const node &b)const{
return abs(x)>abs(b.x);
}
};
priority_queue<node>q;
int n,m,cnt,tmp,a[N],b[N],pre[N],nxt[N];
int main(){
n=read(),m=read();
for(int i=;i<=n;i++){
a[++tmp]=read();
if(!a[tmp])tmp--;
} b[++cnt]=a[];
for(int i=;i<=tmp;i++){
if((a[i]>&&a[i-]>)||(a[i]<&&a[i-]<))b[cnt]+=a[i];
else{
if(cnt==&&b[cnt]<)cnt--;
b[++cnt]=a[i];
}
}
if(b[cnt]<)cnt--; int ans=,tot=;
for(int i=;i<=cnt;i++){
if(b[i]>)ans+=b[i],tot++;
q.push(node(b[i],i));
} for(int i=;i<=cnt+;i++)pre[i]=i-,nxt[i]=i+;
pre[]=;nxt[cnt+]=cnt+;
b[]=b[cnt+]=-INF; while(tot>m){
node p=q.top();q.pop();
if(b[p.y]!=p.x)continue;
ans-=abs(p.x);
b[p.y]=b[pre[p.y]]+b[nxt[p.y]]+p.x;
b[pre[p.y]]=b[nxt[p.y]]=-INF;
q.push(node(b[p.y],p.y));
pre[p.y]=pre[pre[p.y]];nxt[pre[p.y]]=p.y;
nxt[p.y]=nxt[nxt[p.y]];pre[nxt[p.y]]=p.y;
tot--;
}
printf("%d\n",ans);
return ;
}
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/ +
+++++++++++++++++++++++++++++++++++++++++++