种树
题目描述
cyrcyr今天在种树，他在一条直线上挖了n个坑。这n个坑都可以种树，但为了保证每一棵树都有充足的养料，cyrcyr不会在相邻的两个坑中种树。而且由于cyrcyr的树种不够，他至多会种k棵树。假设cyrcyr有某种神能力，能预知自己在某个坑种树的获利会是多少（可能为负），请你帮助他计算出他的最大获利。
输入输出格式
输入格式：
第一行，两个正整数n,k。
第二行，n个正整数，第i个数表示在直线上从左往右数第i个坑种树的获利。
输出格式：
输出1个数，表示cyrcyr种树的最大获利。
输入输出样例
输入样例#1：
6 3
100 1 -1 100 1 -1
输出样例#1：
200
说明
对于20%的数据，n<=20。
对于50%的数据，n<=6000。
对于100%的数据，n<=500000，k<=n/2,在一个地方种树获利的绝对值在1000000以内。
题解
注意到题目中的限制条件，如果在一个坑中种了树，那么这个坑两边的坑就不可以再种树
那么就有这种情况出现，对任意一个坑id，其左边的坑(l[id])及(r[id])，选择(max(v[id],v[l[id]]+v[r[id]]))
正解其实为优先队列（大根堆），首先将所有的坑全部丢入堆中维护，然后最多种满k个坑，所以从1枚举到k，可以不种满，这种情况下肯定是因为种下这棵树的价值是负的，对我们来说没有意义
1~k的循环中每次取出堆顶，直接将其加到ans中（这肯定是不对的，但是之后我们会进行比较，即事实上我们的堆中维护的是(v[l[id]]+v[r[id]]-v[id].)
所以下次取出来后，如果这是一个正数，那么我们实际上加的是(v[l[id]]+v[r[id]])，将其与左右两个坑的值得和比较，然后作差丢入堆中，并将这三个点全部打上标记（不管选择哪种方案这三个坑都不能再使用了）.
然后将这个值赋给在n个坑之后的空位中，即安排一个变量num，初始值为n，并将这个坑num左端点链到(l[l[id]]),右端点链到(r[r[id]])（因为(l[id],r[id])这两个坑都是不能用的），再维护其左右端点
Code
lol l1=l[x.id],r1=r[x.id];
l[num]=l[l1];r[num]=r[r1];
r[l[num]]=num;l[r[num]]=num;
AC代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#define in(i) (i=read())
using namespace std;
typedef long long lol;
lol read()
{
lol ans=0,f=1;
char i=getchar();
while(i<'0'||i>'9') {
if(i=='-') f=-1;
i=getchar();
}
while(i>='0' && i<='9'){
ans=(ans<<1)+(ans<<3)+i-'0';
i=getchar();
}
return ans*f;
}
const lol N=500000;
lol n,k;
struct node{
lol val,id;
}t[N+10];
priority_queue<node>q;
bool operator < (node a,node b){
return a.val<b.val;
}
lol l[N+10],r[N+10],a[N+10],vis[N+10];
int main()
{
lol ans=0;
in(n);in(k);
for(lol i=1;i<=n;i++){
in(t[i].val);
t[i].id=i;
a[i]=t[i].val;
l[i]=i-1;r[i]=i+1;
q.push(t[i]);
}
lol num=n;
for(lol i=1;i<=k;i++){
node x=q.top();
q.top();
while(!q.empty() && vis[x.id]){
x=q.top();
q.pop();
}
if(x.val<0) break;
ans+=x.val;num++;
vis[x.id]=1;
vis[l[x.id]]=1;
vis[r[x.id]]=1;
lol l1=l[x.id],r1=r[x.id];
l[num]=l[l1];r[num]=r[r1];
r[l[num]]=num;l[r[num]]=num;
a[num]=a[l1]+a[r1]-a[x.id];
q.push((node){a[num],num});
}
cout<<ans<<endl;
return 0;
}