就是堆+链表，十分像 数据备份 对吧？

把相邻的正数和相邻的负数合并成一整个正数块和负数块，最后只剩一些交替相间的正块与负块了吧？

显然，正块的个数<=m时，全部选走就获得了最大权值，否则我们可能需要选一些负块来获得最优解。

然而弱不经风的我调了四个小时链表和预处理QAQ。。。

千万不要犯此种错误：

n=g(),m=g();    for(R i=1;i<=n;++i) a[i]=g();    vl[cnt]=a[1],pre[0]=0;    for(R i=2;i<=n;++i) if(sgn(a[i])==sgn(a[i-1])&&sgn(a[i])) vl[cnt]+=a[i];//,cnt==1?cerr<<"%"<
     
      <<" ":cerr<<"";        else if(sgn(a[i]))vl[++cnt]=a[i],nxt[cnt-1]=cnt,pre[cnt]=cnt-1; nxt[cnt]=0;
     

上面这种写法会吧中间有0的同号块分成两块。。。。

AC代码：

#include
     
      #include
      
       #include
       
        #define R register intusing namespace std;const int N=100010; int cnt,n,m,pst,neg,tot,ans=0;int a[N],vl[N],pre[N],nxt[N];bool vis[N];struct node{    int vl,pos;    node() {}    node(int vvl,int ppos):vl(vvl),pos(ppos){}    bool operator <(const node& y)const {
   return vl>y.vl;}};priority_queue
        
          q;inline int g() {    R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;    do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;}inline int abs(int x) {
   return x>0?x:-x;}signed main() {    n=g(),m=g();    for(R i=1;i<=n;++i) {        a[i]=g();        if(a[i]>0){pst+=a[i]; neg&&cnt?vl[++cnt]=neg,neg=0:neg=0;}        if(a[i]<0){neg+=a[i]; pst?vl[++cnt]=pst,pst=0:pst=0;}    } pst?vl[++cnt]=pst:pst=0;    for(R i=1;i<=cnt;++i) {        q.push(node(abs(vl[i]),i));        vl[i]>0?++tot,ans+=vl[i]:vl[i]=-vl[i];        nxt[i]=i+1,pre[i]=i-1;    } nxt[cnt]=0;    for(R i=1;i+m<=tot;++i) {        register node tmp=q.top();q.pop();        while(vis[tmp.pos]&&!q.empty()) tmp=q.top(),q.pop();        if(vis[tmp.pos]) break;        ans-=tmp.vl; if(q.empty()) break;        R pos=tmp.pos;        if(!pre[pos]) vis[nxt[pos]]=vis[pos]=true,pre[nxt[nxt[pos]]]=0;        else if(!nxt[pos]) vis[pre[pos]]=vis[pos]=true,nxt[pre[pre[pos]]]=0;        else {            vis[pre[pos]]=vis[nxt[pos]]=true;            tmp.vl=vl[pos]=vl[pre[pos]]+vl[nxt[pos]]-vl[pos];            if(nxt[nxt[pos]]) pre[nxt[nxt[pos]]]=pos;            if(pre[pre[pos]]) nxt[pre[pre[pos]]]=pos;            pre[pos]=pre[pre[pos]],nxt[pos]=nxt[nxt[pos]];            q.push(tmp);        }    } printf("%d\n",ans);}
        
       
      
     

 

---

 

2019.04.06