题目描述
cyrcyr今天在种树，他在一条直线上挖了n个坑。这n个坑都可以种树，但为了保证每一棵树都有充足的养料，cyrcyr不会在相邻的两个坑中种树。而且由于cyrcyr的树种不够，他至多会种k棵树。假设cyrcyr有某种神能力，能预知自己在某个坑种树的获利会是多少（可能为负），请你帮助他计算出他的最大获利。
输入输出格式
输入格式：
第一行，两个正整数n,k。
第二行，n个正整数，第i个数表示在直线上从左往右数第i个坑种树的获利。
输出格式：
输出1个数，表示cyrcyr种树的最大获利。
输入输出样例
说明
对于20%的数据，n<=20。
对于50%的数据，n<=6000。
对于100%的数据，n<=500000，k<=n/2,在一个地方种树获利的绝对值在1000000以内。
好像是堆的固定套路，首先肯定是每次取最大的正数，但是可能有差错，如70，100，80，如果只取两个，显然是150。
这时就需要撤回操作，即每弹出一个数时，将一个值为左右两边数的值减去本身加入堆，如果这个被选，就相当于撤回，选了旁边的两个数。
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int N=;
int n,k,l[N],r[N];
long long ans;
bool inq[N];
struct node
{
int id;
long long v;
bool operator <(node c)const
{
return v<c.v;
}
}a[N],t;
priority_queue<node>q;
int main()
{
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++)
{
scanf("%lld",&a[i].v);
a[i].id=i;
q.push(a[i]);
l[i]=i-;
r[i]=i+;
}
while(k--)
{
while(inq[q.top().id])
q.pop();
if(q.top().v<=)
break;
t=q.top();
q.pop();
ans+=t.v;
inq[l[t.id]]=inq[r[t.id]]=;
a[t.id].v=t.v=a[l[t.id]].v+a[r[t.id]].v-t.v;
l[t.id]=l[l[t.id]],r[t.id]=r[r[t.id]];
r[l[t.id]]=t.id,l[r[t.id]]=t.id;
q.push(t);
}
printf("%lld\n",ans);
return ;
}