就是堆+链表，十分像 数据备份 对吧？
把相邻的正数和相邻的负数合并成一整个正数块和负数块，最后只剩一些交替相间的正块与负块了吧？
显然，正块的个数<=m时，全部选走就获得了最大权值，否则我们可能需要选一些负块来获得最优解。
然而弱不经风的我调了四个小时链表和预处理QAQ。。。
千万不要犯此种错误：
n=g(),m=g();
for(R i=;i<=n;++i) a[i]=g();
vl[cnt]=a[],pre[]=;
for(R i=;i<=n;++i) if(sgn(a[i])==sgn(a[i-])&&sgn(a[i])) vl[cnt]+=a[i];//,cnt==1?cerr<<"%"<<vl[cnt]<<" ":cerr<<"";
else if(sgn(a[i]))vl[++cnt]=a[i],nxt[cnt-]=cnt,pre[cnt]=cnt-; nxt[cnt]=;
上面这种写法会吧中间有0的同号块分成两块。。。。
AC代码：
#include<cstdio>
#include<iostream>
#include<queue>
#define R register int
using namespace std;
const int N=;
int cnt,n,m,pst,neg,tot,ans=;
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<node> q;
inline int g() {
R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;
do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;
}
inline int abs(int x) {return x>?x:-x;}
signed main() {
n=g(),m=g();
for(R i=;i<=n;++i) {
a[i]=g();
if(a[i]>){pst+=a[i]; neg&&cnt?vl[++cnt]=neg,neg=:neg=;}
if(a[i]<){neg+=a[i]; pst?vl[++cnt]=pst,pst=:pst=;}
} pst?vl[++cnt]=pst:pst=;
for(R i=;i<=cnt;++i) {
q.push(node(abs(vl[i]),i));
vl[i]>?++tot,ans+=vl[i]:vl[i]=-vl[i];
nxt[i]=i+,pre[i]=i-;
} nxt[cnt]=;
for(R i=;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]]]=;
else if(!nxt[pos]) vis[pre[pos]]=vis[pos]=true,nxt[pre[pre[pos]]]=;
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
