种树

在长度为 $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);
}