【算法】贪心+堆
【题意】n个数字的序列，要求选择互不相邻的k个数字使和最大。
【题解】
贪心，就是按一定顺序选取即可最优，不会反悔。
考虑第一个数字选择权值最大的，那么它相邻的两个数字就不能选择，那么我们可以把这三个数字视为一个整体。操作为将pre[pre[x]]和x和suc[suc[x]]连接起来。
由于可能依然有选择相邻两个数字的可能性，将中间的权值置为A[pre[x]]+A[suc[x]]-A[x]，这个权值记录在中间，但实际上代表相邻三个数字的新权值。
若再次选择这个区间，那么就是把区间更新到周围五个数字了(这里的数字有可能已经是一段区间)，如此可以不断扩大。
贪心原理：若没有间隔种的限制，每次都取大就是最优的。那么多了这个限制之后，取大依然优但却会影响旁边两个数字的选择。
为了使我们依然能贪心，就设置一个反悔的机会，即设置一个新权值。那么如果非要选择旁边两个就相当于选择中间的权值两次，每次把影响区间扩大2并视之为一个数字。
因为贪心就不会反悔的性质，既然会选择这个决策就一定不会悔改。这个反悔的机会实质上是扩大你选择数字的影响范围，一旦扩大就一定不会反悔，因为一定是最优的。
每次出现新权值用堆维护。记得开始先特判无法种k棵的情况，因为后面很难判断。
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int maxn=200010; struct cyc{ int num,ord; bool operator < (const cyc &x)const {return num<x.num;} }qp; priority_queue<cyc>q; int a[maxn],pre[maxn],suc[maxn],n,k; bool f[maxn]; void del(int x) { f[x]=1; suc[pre[x]]=suc[x]; pre[suc[x]]=pre[x]; suc[x]=pre[x]=0; } int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); q.push((cyc){a[i],i}); pre[i]=i-1;suc[i]=i+1; } pre[1]=n;suc[n]=1; int ans=0; if(k>n/2){printf("Error!");return 0;} for(int i=1;i<=k;i++) { while(f[q.top().ord])q.pop(); qp=q.top();q.pop(); ans+=qp.num; int A=pre[qp.ord],B=suc[qp.ord]; a[qp.ord]=a[A]+a[B]-qp.num; del(pre[qp.ord]);del(suc[qp.ord]); q.push((cyc){a[qp.ord],qp.ord}); } printf("%d",ans); return 0; }