发布于

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;
}

 

发布于

lp3084 USACO13OPEN 照片 Photo

传说这一题可以用差分约束，不过我个人的第一眼想法是\(DP\)。
首先我们令\(f_{i}\)为，第\(i\)个奶牛有斑点，\(DP\)到第\(i\)个奶牛，此时最多有多少只奶牛。
我们可以发现两点：一个区间最多有1个有斑点的奶牛，且一个区间最少有1个有斑点的奶牛。
对于当前的点，我们很容易可以知道，所有覆盖当前点的区间，在其他的地方都不能有有斑点的奶牛。
这也就等价于，转移是必须从包含\(f_{i}\)的所有区间中的左端点的最小值开始转移的。
与此同时，我们还必须明白，因为每个区间最少有一个有斑点的奶牛，因而为了保证满足提议，转移点到\(f_{i}\)之间的所有区间不能有空的。
这也就等价于，所有不包含\(f_{i}\)（当然显然区间右端点要小于\(i\)）的区间，它们的左端点中的最大值必须要小于转移点。这样才能上述性质。
此时我们只需要预处理出包含点i且左端点最小的区间，以及右端点小于\(i\)且左端点最大的区间。我们分别用\(e_{i}\)和\(s_{i}\)表示。
对于读入的每一组\(a,b\)，我们做如下处理：
使用\(a\)来更新\(s_{b+1}\)。这是因为，从\(a\)开始的区间必然不包含\(b+1\)，因此可以这样更新。
使用\(a-1\)来更新\(e_{b}\)。这是因为，从\(a\)开始的区间必然包含\(b\)。
故，更新方法为：
$$ s_{b+1}=Max(s_{b+1},a),e_{b}=Min(e_{b},a-1); $$
然后，对于这样更新得到的结果，我们贪心地处理。
对于\(s\)，我们发现，所有对于点\(i-1\)合法的区间——也就是右端点小于\(i-1\)的区间，一定不包含\(i\)。所以得到：
$$ s_{i}=Max(s_{i},s_{i-1}); $$
对于\(e\)，我们发现，所有对于点\(i+1\)最优的区间——也就是包含\(i+1\)且左端点最小的区间，一定包含\(i\)，否则它对于\(i\)一定不会更优。所以得到：
$$ e_{i}=Min(e_{i+1},e_{i}); $$
由是我们得到了DP需要的两个辅助数组，从而可以开始\(DP\)。
但这个时候我们可以发现，这样子动态确定最大值，如果使用暴力枚举，需要的复杂度是\(O(n)\)的，对于\(2E5\)的数据，通过会很困难。
这时候考虑优化，不过很容易可以发现是单调队列优化。
于是问题得解。

交上去WA10。
这是什么原因呢？
仔细研究一下，发现还是细节的问题。对于-1的特判没有清楚。
修改之后AC。

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))

int n,m,f[200005],s[200005],e[200005];
struct data{
	int v;
	int id;
};
deque<data> q;
inline void psh(int i){
	data x=(data){f[i],i};
	while(!q.empty()&&q.back().v<x.v){
		q.pop_back();
	}
	q.push_back(x);
}
inline int gt(const int &i){
	while(!q.empty()&&q.front().id<s[i]){
		q.pop_front();
	}
	return q.empty()?-1:q.front().v;
}
void init(){
	scanf("%d%d",&n,&m);
	int a,b;
	for(int i=1;i<=n+1;++i){
		e[i]=i-1; 
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d",&a,&b);
		s[b+1]=Max(s[b+1],a),e[b]=Min(e[b],a-1);
	}
	for(int i=2;i<=n+1;++i){
		s[i]=Max(s[i],s[i-1]);
	}
	for(int i=n;i>=1;--i){
		e[i]=Min(e[i+1],e[i]); 
	}
	f[0]=0;
	psh(0);
	int j=1,nw;
	for(int i=1;i<=n+1;++i){
		while(j<=e[i]&&j<=n){
			psh(j);
			++j;
		}
		nw=gt(i);
		f[i]=(nw==-1)?-1:nw+(int)(i<=n);
	}
	printf("%d",f[n+1]);
}
int main(){
	init();
	return 0;
}