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

发表评论

您的电子邮箱地址不会被公开。