记录编号	57484	评测结果	AAAAAAAAAA
题目名称	[POI 1997] 阶梯教室设备利用	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.027 s
提交时间	2013-04-10 16:12:41	内存使用	2.10 MiB

#include<iostream>
#include<cstdio>
#include<deque>
#include<algorithm>
using namespace std;
const int NSIZE=100001;
class Segment{
public:
	int l,r;//左右端点
	int v;//权值,即被几个人预言
	bool e;//是否存在
};
Segment c[NSIZE];
int n;
bool cmp(Segment a,Segment b){
	if(a.r<b.r) return true;
	if(a.r>b.r) return false;
	if(a.l<=b.l) return true;
	return false;
}
int main(){
	freopen("rez.in","r",stdin);
	freopen("rez.out","w",stdout);
	int f[NSIZE]={0};
	scanf("%d",&n);
	int i,a,b;
	int L=0;
	for(i=1;i<=n;i++){
		scanf("%d%d",&a,&b);
		c[i].l=a+1,c[i].r=b+1;
		L=max(L,b+1);
		c[i].v=b-a;
	}
	sort(c+1,c+n+1,cmp);
	f[0]=0;
	int now=1;
	for(i=1;i<=L;i++){
		f[i]=f[i-1];
		while(c[now].r==i){
			if(f[c[now].l]+c[now].v>f[i]) f[i]=f[c[now].l]+c[now].v;
			now++;
		}
	}
	printf("%d\n",f[L]);
	return 0;
}