用堆维护双向链表来贪心。。。
数据范围显然不容许O(nm)的傻逼dp>_<。。而且dp光是状态就n*m个了。。显然没法优化
大概就会想到贪心乱搞了吧。。。一开始想贪心地通过几段小的负数把正数连接成一段，但到底是要连接在一起还是直接扔掉不好判断
然后就跑去翻题解了。。。题解讲的挺好的，连我都看懂了>_<。。题解网址：http://www.cnblogs.com/tuigou/p/4868127.html
虽然选正数和负数的意义不同，但实际的操作都是把两边的数合并起来。还有就是，对于在左端或右端的负数，把它删去后并不会减少当前选取的段数。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstdlib>
#include<cmath>
#define ll long long
using namespace std;
const int maxn=;
struct zs{
int id;
};
priority_queue <zs>q;
int a[maxn],cnt,pre[maxn<<],next[maxn<<],v[maxn<<];
int i,j,n,m,zsnum,ans;
bool del[maxn<<]; int ra,fh;char rx;
inline int read(){
rx=getchar(),ra=,fh=;
while((rx<''||rx>'')&&rx!='-')rx=getchar();
if(rx=='-')fh=-,rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra*fh;
}
bool operator <(zs a,zs b){return abs(v[a.id])>abs(v[b.id]);}
int main(){
n=read(),m=read();if(!m){puts("");return ;}
for(i=;i<=n;i++)a[i]=read();cnt=;
for(i=;i<=n;v[cnt]+=a[i++])
if((ll)a[i]*(ll)v[cnt]<||!cnt)cnt++;
for(i=;i<=cnt;i++)if(v[i]>)zsnum++,ans+=v[i];
if(zsnum>m){
for(i=;i<=cnt;i++)q.push((zs){i}),pre[i]=i-,next[i]=i+;//,printf(" %d",v[i]);puts("");
pre[]=next[cnt]=;
for(i=zsnum-m;i;i--){
while(!q.empty()&&del[q.top().id])q.pop();if(q.empty())break;
int x=q.top().id,pr=pre[x],nex=next[x]; q.pop(),ans-=abs(v[x]),del[x]=;
if(!(pr&&nex)){
if(v[x]<)i++,ans+=abs(v[x]);
if(pr)next[pr]=;if(nex)pre[nex]=;
}
else{
del[pr]=del[nex]=;
v[++cnt]=v[pr]+v[x]+v[nex];
q.push((zs){cnt});
if(pre[pr])pre[cnt]=pre[pr],next[pre[cnt]]=cnt;
if(next[nex])next[cnt]=next[nex],pre[next[cnt]]=cnt;
}
}
}
printf("%d\n",ans);
return ;
}