种树
在长度为 \(n\) 的数列中选择至少 \(k\) 个数字，他们都有价值，使得没有相邻的数字被取到，且数字之和最大。
求这个最大的数字之和。
我们考虑一个反悔贪心，首先用一个链表来维护数列，然后，每次贪心的选择最大的数字，并标记左右不可用。
但是这个贪心显然是错的，我们再直接将这三个数字合并为一个，价值为 \(a_L+a_R-a_i\)，意思大家应该懂。
显然这个数字，选择它相当于改选 \(a_i\) 两边的数字，这就是我们的反悔了。
再加上一个大根堆维护即可。
需要注意的是，其实这里我们选择的数字不一定是答案方案中的数字，而是我们不断启用反悔机制，不断算上增量，得到最终答案。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
priority_queue<pair<LL,LL> >p;
const LL N=1e6;
LL n,k,a[N],L[N],R[N],len,vis[N],ans;
int main()
{
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
p.push({a[i],i});
L[i]=i-1,R[i]=i+1;
}
len=n+1;
for(int i=1;i<=k;i++)
{
while(!p.empty()&&vis[p.top().second]==1)p.pop();//无法选的
if(p.empty()||p.top().first<0)break;//无法选或者选只能变小
LL t=p.top().second,v=p.top().first;
ans+=v;
p.pop();
LL l=L[t],r=R[t];
vis[t]=1,vis[l]=1,vis[r]=1;//标记
a[++len]=a[r]+a[l]-a[t];
L[len]=L[l],R[len]=R[r],R[L[l]]=len,L[R[r]]=len;//合并处理
p.push({a[len],len});
}
printf("%lld",ans);
}
种树 2
在长度为 \(n\) 的环中选择至少 \(k\) 个数字，他们都有价值，使得没有相邻的数字被取到，且数字之和最大。
求这个最大的数字之和。
其实当你思考上一个问题的时候，你就会觉得这个链表很有意思，是时候展示链表的含金量了。
我们利用链表的特性，将数组首尾相连即可。
我们只需要添加以下代码：
L[1]=n,R[n]=1;
种树 3
在长度为 \(n\) 的环中强制选择 \(k\) 个数字，他们都有价值，使得没有相邻的数字被取到，且数字之和最大。
求这个最大的数字之和。
如果无解输出
Error!。
依然是一个变化不大的题，首先，如何判断无解，根据限定条件，易得：
if(n<2*k)
{
puts("Error!");
return 0;
}
添加至输入后即可。
注意到源代码中有这样一行：
if(p.empty()||p.top().first<0)break;//无法选或者选只能变小
无解已经判定了，这道题强制选择 \(k\) 个，所以删去即可。
核心代码如下：
for(int i=1;i<=k;i++)
{
while(!p.empty()&&vis[p.top().second]==1)p.pop();
LL t=p.top().second,v=p.top().first;
ans+=v;
p.pop();
LL l=L[t],r=R[t];
vis[t]=1,vis[l]=1,vis[r]=1;
a[++len]=a[r]+a[l]-a[t];
L[len]=L[l],R[len]=R[r],R[L[l]]=len,L[R[r]]=len;
p.push({a[len],len});
}
Guard Duty
给定\(n\)个时间点。每个区间都以某两个时间点为左右端点，且每个区间的代价定义为端点的时间之差。
你要选择 \(k\) 个连续的区间，保证这个 \(k\) 个连续的区间没有交集，且代价总和最小。
直觉告诉我们应该从大到小排一个序，然后选相邻的数字，这样代价最小，且这一点显然，在此不证明。
我们用差分处理出相邻的数字形成区间的价值，然后我们发现这里相邻的区间占有相同的点，不可同时选择，也就是相邻的区间不可选择。
那这个反悔贪心就很显然了。
注意这里是最小值，所以你需要搞一个小根堆，而且左右边界要附一个较大的值。
#include<bits/stdc++.h>
#define LL long long
#define T pair<LL,LL>
using namespace std;
priority_queue<T,vector<T>,greater<T> >p;
const LL N=1e6;
LL n,k,a[N],L[N],R[N],len,vis[N],ans;
int main()
{
scanf("%lld%lld",&k,&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
}
sort(a+1,a+n+1);
for(int i=1;i<n;i++)
{
a[i]=a[i+1]-a[i];
p.push({a[i],i});
L[i]=i-1,R[i]=i+1;
}
a[0]=a[n]=1e18;
len=n;
for(int i=1;i<=k;i++)
{
while(!p.empty()&&vis[p.top().second]==1)p.pop();
LL t=p.top().second,v=p.top().first;
ans+=v;
p.pop();
LL l=L[t],r=R[t];
vis[t]=1,vis[l]=1,vis[r]=1;
a[++len]=a[r]+a[l]-a[t];
L[len]=L[l],R[len]=R[r],R[L[l]]=len,L[R[r]]=len;
p.push({a[len],len});
}
printf("%lld",ans);
}