lp2519 HAOI2011 problem a

我们为每个考生设置一个可能的区间。这个区间的左端点是l=a+1,右端点是r=n-b。
仔细观察,会发现,这个可能的区间,就是和这个考生同分(包括这个考生)的考生的数量。
那么显然,如果这个可能的区间不存在,那么这个考生在撒谎;如果在同一个区间里面有超过区间长度的考生数,那么也是不合法的。
我们仔细想想,还有什么情况是冲突的。我们发现,说真话的考生所在的区间是不能重合的。
于是问题就转化为一个类似于背包的问题。我们可以将这些区间排序,那么不妨设f[i]表示第i个区间为真的情况下的最大数量。
首先,如果右端点递减,我们可以考虑用一个单调队列来维护这个东西。
在这种情况下,可以维护一个r值递增,f值递增的单调队列。
每一次把新的右端点插入到单调队列的右端,然后如果右端的f值比当前的f值小,那么就把右端的f值给干掉。
然而,实际上,右端点是无单调性的,所以可能存在这样一种情况:新插入的点的r值更小,而f值也更小。这时候就没有办法判断是否要删掉单调队列末端的点了。
想象一下在这种情况下要怎么做。在这种情况下,我们可以将新插入的点插到r值刚好比它小的那个点前面,然后把所有r值比它大而f值比它小的点都删掉。
要如何维护呢?直观地想是使用平衡树,但是我们可以使用map来完成这个操作。
然而,这样涉及到复杂的iterator操作。我并不是很会。
我们考虑另外一种想法。我们令f[i]表示以i为当前访问过的最右端点的情况下的最优值。
那么,我们可以记录每一个右端点的所有左端点,然后枚举这些左端点并转移,就可以得出答案。
注意:一个区间的权值要与它的长度取min!
注意:这样求出来的答案是真的数量,要用n减去它!

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
using namespace std;

inline int Max(int A,int B){
	return A>B?A:B;
}
inline int Min(int A,int B){
	return A<B?A:B;
}
typedef pair<int,int> pii;
const int N=100005;
int n;
int f[N];
vector<int> lst[N];
map<pii,int> mp;
void init(){
	scanf("%d",&n);
	int x,y,l,r;
	for(int i=1;i<=n;++i){
		scanf("%d%d",&x,&y);
		l=x+1,r=n-y;
		if(l>r){
			continue;
		}
		if(++mp[(pii){l,r}]==1){
			lst[r].push_back(l);
		}
	}
	for(int i=1;i<=n;++i){
		f[i]=f[i-1];
		for(int j=0;j<lst[i].size();++j){
			f[i]=Max(f[i],f[lst[i][j]-1]+Min(i-lst[i][j]+1,mp[(pii){lst[i][j],i}]));
		}
	}
	printf("%d\n",n-f[n]);
}
int main(){
	init();
	return 0;
}

发表评论

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