lp1792 国家集训队 种树

首先拿到题面很容易可以想到的是状压DP,状态转移方程很容易可以推出来。
但是这么做的复杂度是\(O(n^2)\)的,只能拿到50分。
我们深入地考虑这一题的性质,我们发现,对于这个环,如果取用了上面的某一个点,那么这个点的两个邻点都不可取。
贪心地依据权值从大到小考虑,如果一个点的两个邻点加起来都不如它大的话,那么取邻点中的任意一个都不如取这个点。
如果这个点的两个邻点加一起比它大,那就考虑两种情况,一种情况是选择这个点,一种情况是选择这个点的两个邻点。
(很容易可以知道,如果两个邻点只选一个,那是一定没有选这个点优的。)
我们考虑先取了这个点,再转变为取这个点的两个邻点的情况。这种情况下,总权值就会减去这个点的权值,并且加上这个点的两个邻点的权值。
我们考虑一个有趣的性质。如果一个点的两个邻点都选取了,那么影响到的“不可被选取区域”的大小,是和三个都选是相同的。
因此,我们考虑究竟应该选取这个点还是这个点的两个邻点。我们考虑每当挖去一个点的时候,都把它的两个邻点标记为消失。
这时候对不可选取区域的影响已经确定了,因此只要确定对对权值的影响。
那么我们考虑建一个虚点,替代在贪心选取的那个点以及两个相邻的位置。这个虚点的权值相当于邻点的权值和减去原点的权值。
对于这个虚点,我们把它当做这个环上本来就存在的一个点来处理即可。
所以可以考虑用堆+双向链表来维护。

顺便提一句,这是一道三倍经验题,它的亲人们:
lp3620 APIO/CTSC2007 数据备份,lp1484 种树
前者只要差分一下,边转点,改大小判断以后的边界,再改一下单调队列;后者只要判一下负数情况。

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;

int n,m,a[200005],l[200005],r[200005],nw,nw2;
bool ext[200005];
typedef pair<int,int> pii;
priority_queue<pii> q;
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		q.push((pii){a[i],i});
		ext[i]=0;
	}
	if(m>(n>>1)){
		puts("Error!");
		return;
	}
	for(int i=2;i<=n;++i){
		l[i]=i-1;
	}
	l[1]=n;
	for(int i=1;i<n;++i){
		r[i]=i+1;
	}
	r[n]=1;
	long long ans=0;
	for(int i=1;i<=m;++i){
		while(!q.empty()&&ext[q.top().second]){
			q.pop();
		}
		nw=q.top().second;
		ans+=q.top().first;
		ext[l[nw]]=1,ext[r[nw]]=1;
		nw2=a[l[nw]]+a[r[nw]]-q.top().first;
		a[nw]=nw2;
		l[nw]=l[l[nw]],r[nw]=r[r[nw]];
		r[l[nw]]=nw,l[r[nw]]=nw;
		q.pop();
		q.push((pii){nw2,nw});
	}
	printf("%lld",ans);
}

int main(){
	init();
	return 0;
}

顺便贴一下后面两题的代码:

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int n,m,a[500005],l[500005],r[500005],nw,nw2;
bool ext[500005];
//lp1484 种树 
typedef pair<int,int> pii;
priority_queue<pii> q;
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		q.push((pii){a[i],i});
		ext[i]=0;
	}
	if(m>(n>>1)){
		puts("Error!");
		return;
	}
	for(int i=1;i<=n;++i){
		l[i]=i-1;
	}
	for(int i=1;i<=n;++i){
		r[i]=i+1;
	}
	long long ans=0;
	for(int i=1;i<=m;++i){
		while(!q.empty()&&ext[q.top().second]){
			q.pop();
		}
		if(q.top().first<0){
			break;
		} 
		nw=q.top().second;
		ans+=q.top().first;
		ext[l[nw]]=1,ext[r[nw]]=1;
		nw2=a[l[nw]]+a[r[nw]]-q.top().first;
		a[nw]=nw2;
		l[nw]=l[l[nw]],r[nw]=r[r[nw]];
		r[l[nw]]=nw,l[r[nw]]=nw;
		q.pop();
		q.push((pii){nw2,nw});
	}
	printf("%lld",ans);
}

int main(){
	init();
	return 0;
}
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
int n,m,a[100005],l[100005],r[100005],nw,nw2;
bool ext[100005];
//lp3620 APIOCTSC2007 数据备份 
typedef pair<int,int> pii;
priority_queue< pii,vector<pii>,greater<pii> > q;
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		ext[i]=0;
	}
	for(int i=n;i>=1;--i){
		a[i]-=a[i-1];
	}
	for(int i=1;i<n;++i){
		a[i]=a[i+1];
		q.push((pii){a[i],i});
	} 
	a[0]=a[n]=0x3f3f3f3f; 
	if(m>(n>>1)){
		puts("Error!");
		return;
	}
	for(int i=1;i<n;++i){
		l[i]=i-1;
	}
	for(int i=1;i<n;++i){
		r[i]=i+1;
	}
	long long ans=0;
	for(int i=1;i<=m;++i){
		while(!q.empty()&&ext[q.top().second]){
			q.pop();
		}
		nw=q.top().second;
		ans+=q.top().first;
		ext[l[nw]]=1,ext[r[nw]]=1;
		nw2=a[l[nw]]+a[r[nw]]-q.top().first;
		a[nw]=nw2;
		l[nw]=l[l[nw]],r[nw]=r[r[nw]];
		r[l[nw]]=nw,l[r[nw]]=nw;
		q.pop();
		q.push((pii){nw2,nw});
	}
	printf("%lld",ans);
}

int main(){
	init();
	return 0;
}