题意：
给一个序列，求不超过m个连续的部分，使元素和最大。序列大小≤100000
题解：
先把连续的正数和负数合并起来，接着如果正数个数小于m则全选，否则需要确定去掉那个正数或合并哪个正数。初始ans设为所有正数和，将所有的数按绝对值大小放入堆中，然后重复m-正数个数操作：每次选取绝对值最小的数，如果是负数且它在边界处则重新选，否则将这个数删除并将两边的数合并，同时ans-=该数绝对值。该操作的意义在于：如果删去的是正数表示不选它，否则表示选这个负数以将左右的的正数合并起来。类似于1150，我用链表和STLset维护这个过程。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 100010
using namespace std; inline int read(){
char ch=getchar(); int f=,x=;
while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}
while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();
return f*x;
}
int n,m,a[maxn],b[maxn],tot,ans;
struct sn{
int pos,v;
bool operator < (const sn &x)const{return v!=x.v?v<x.v:pos<x.pos;}
};
set<sn>s;
struct nd{int v,l,r; bool bit;}; nd nds[maxn];
int main(){
n=read(); m=read(); inc(i,,n)b[i]=read();
int last=; inc(i,,n){
if(b[i]==)continue; if(!last||(last>^b[i]>))a[++tot]=b[i];else a[tot]+=b[i]; last=b[i];
}
n=tot; tot=; inc(i,,n)if(a[i]>)tot++,ans+=a[i];
if(tot>m){
inc(i,,n){s.insert((sn){i,abs(a[i])}); nds[i]=(nd){abs(a[i]),i-,i+>n?:i+,a[i]>};}
inc(i,,tot-m){
set<sn>::iterator xx; int x;
while(){
xx=s.begin(); x=xx->pos; s.erase(xx);
if((!nds[x].l||!nds[x].r)&&!nds[x].bit){
if(!nds[x].l)nds[nds[x].r].l=; if(!nds[x].r)nds[nds[x].l].r=;
}else break;
}
ans-=nds[x].v;
if(!nds[x].l&&!nds[x].r)continue;
else if(!nds[x].r)nds[nds[x].l].r=;
else if(!nds[x].l)nds[nds[x].r].l=;
else{
nds[x].v=nds[nds[x].l].v+nds[nds[x].r].v-nds[x].v; nds[x].bit=nds[nds[x].l].bit;
xx=s.find((sn){nds[x].l,nds[nds[x].l].v}); s.erase(xx);
xx=s.find((sn){nds[x].r,nds[nds[x].r].v}); s.erase(xx);
s.insert((sn){x,nds[x].v});
nds[x].l=nds[nds[x].l].l; nds[x].r=nds[nds[x].r].r; nds[nds[x].l].r=x; nds[nds[x].r].l=x;
}
}
}
printf("%d",ans); return ;
}
20160905