首页 > 代码库 > 51Nod 1380 夹克老爷的逢三抽一
51Nod 1380 夹克老爷的逢三抽一
Description
一开始有一个环,可以选择删除一个元素获得他的权值,同时删除与它相邻的两个元素,其他元素重新形成环,问能获得的最大价值.
Sol
堆+贪心.
一开始从堆中加入所有元素,然后取出一个元素之后,加入他两边的元素之和-该位置的权值,并把左右两点删除.
一直到取出 \(\frac {n} {3}\) 个元素即可,左右元素可以用链表维护.
这样取出一个元素了以后可以进行反悔的操作,获得另外两个权值.
xyx大爷说只要不相邻那么元素个数使得他必然有一种合法的删除方案.
Code
#include<cstdio>#include<utility>#include<queue>#include<algorithm>#include<iostream>using namespace std;#define mpr(a,b) make_pair(a,b)typedef long long LL;const int N = 100005;int n,b[N],nxt[N],pre[N];LL a[N];LL ans,tmp;priority_queue<pair<LL,int> > q;inline LL in(LL x=0,char ch=getchar()){ while(ch>‘9‘||ch<‘0‘) ch=getchar(); while(ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();return x; }int main(){ n=in(); for(int i=1;i<=n;i++) a[i]=in(),nxt[i]=i+1,pre[i]=i-1; nxt[n]=1,pre[1]=n; for(int i=1;i<=n;i++) q.push(mpr(a[i],i)); for(int i=1,pos,x;i*3<=n;){ x=q.top().first,pos=q.top().second,q.pop(); if(x<=0) break; if(b[pos]) continue;++i; //cout<<pos<<" "<<x<<endl; ans+=x; tmp=a[nxt[pos]]+a[pre[pos]]-x; a[pos]=tmp; q.push(mpr(tmp,pos)); b[nxt[pos]]=1,b[pre[pos]]=1; nxt[pre[pre[pos]]]=pos,pre[nxt[nxt[pos]]]=pos,pre[pos]=pre[pre[pos]],nxt[pos]=nxt[nxt[pos]]; //pre[pos]=pre[pre[pos]],nxt[pos]=nxt[nxt[pos]],nxt[pre[pos]]=pos,pre[nxt[pos]]=pos; }cout<<ans<<endl; return 0;}
51Nod 1380 夹克老爷的逢三抽一
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。