首页 技术 正文
技术 2022年11月23日
0 收藏 325 点赞 3,303 浏览 1742 个字

就是堆+链表,十分像 数据备份 对吧?

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

显然,正块的个数<=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

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:9,254
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:5,692
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:569 阅读:6,531
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:6,302
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:7,942
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:5,102