题意

N个整数组成的序列a[1],a[2],a[3],…,a[n]，将这N个数划分为互不相交的M个子段，并且这M个子段的和是最大的。如果M >= N个数中正数的个数，那么输出所有正数的和。
例如：-2 11 -4 13 -5 6 -2，分为2段，11 -4 13一段，6一段，和为26。

V3是在环上的

题解

和之前bzoj的题差不多
都是贪心+堆+链表维护
这里就不再赘述
如果在环上的话，边界问题反而好搞了。。
代码也短一些
这里给出V3的代码

#include <queue>
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 100005
using namespace std;
typedef long long LL;
struct Node
{LL val,pre,nxt;inline void clear(){val=pre=nxt=0;}
}a[N<<2];
LL n,nn,m,c[N],b[N],mark[N],tot,sum,cnt;
struct ckh
{bool operator()(LL x,LL y){
   return abs(a[x].val)>abs(a[y].val);}
};
priority_queue<int,vector<int>,ckh>q;
inline void merge(LL x)
{LL nxt=a[x].nxt,pre=a[x].pre;if(!mark[pre]){mark[pre]=1;a[x].val+=a[pre].val;a[a[pre].pre].nxt=x,a[x].pre=a[pre].pre;}if(!mark[nxt]){mark[nxt]=1;a[x].val+=a[nxt].val;a[a[nxt].nxt].pre=x,a[x].nxt=a[nxt].nxt;}a[0].clear();
}
int main()
{cin>>n>>m;LL i,calc=1;for(i=1;i<=n;++i){scanf("%I64d",&c[i]);if(c[i])b[++nn]=c[i];}b[0]=-b[1];for(i=1;i<=nn;++i){if(b[i]*b[i-calc]<0)a[++tot].val=b[i],a[tot-1].nxt=tot,a[tot].pre=tot-1;else a[tot].val+=b[i];sum+=(b[i]>0)*b[i];}if (a[tot].val*a[1].val>0){a[1].val+=a[tot].val;tot--;}a[1].pre=tot;a[tot].nxt=1;
/* for (int u=1;u<=tot;u++) printf("%I64d ",a[u].val);printf("\n");*/for(i=1;i<=tot;++i)cnt+=(a[i].val>0),q.push(i);// printf("%I64d\n",cnt);if(cnt<=m){printf("%I64d\n",sum);return 0;}LL x;while(cnt>m){x=q.top();q.pop();// printf("%I64d %I64d\n",x,a[x].val);if(mark[x])continue;sum-=abs(a[x].val),cnt--;merge(x);q.push(x);}cout<<sum;return 0;
}