记录编号	295588	评测结果	AAAAAAAAAA
题目名称	[HAOI 2011]问题A	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.573 s
提交时间	2016-08-13 21:33:37	内存使用	2.68 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
const int maxn=100010;
map<int,int>w[maxn];
map<int,int>::iterator it;
int n,f[maxn],l,r;
int main(){
#define MINE
#ifdef MINE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
#endif
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&l,&r);
		l++;
		r=n-r;
		w[r][l]++;
	}
	f[0]=0;
	for(int i=1;i<=n;i++){
		f[i]=f[i-1];
		for(it=w[i].begin();it!=w[i].end();it++)
			f[i]=max(f[i],f[it->first-1]+min(i-it->first+1,it->second));
	}
	printf("%d",n-f[n]);
	return 0;
}