【算法】贪心+堆
【题意】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=;
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]=;
suc[pre[x]]=suc[x];
pre[suc[x]]=pre[x];
suc[x]=pre[x]=;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
q.push((cyc){a[i],i});
pre[i]=i-;suc[i]=i+;
}
pre[]=n;suc[n]=;
int ans=;
if(k>n/){printf("Error!");return ;}
for(int i=;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 ;
}