记录编号	8622	评测结果	AAAAAAAAAA
题目名称	[POI 1997] 阶梯教室设备利用	最终得分	100
用户昵称	BYVoid	是否通过	通过
代码语言	C++	运行时间	1.607 s
提交时间	2008-11-28 19:05:59	内存使用	0.37 MiB

#include <iostream>
#include <stdlib.h>
 
using namespace std;
 
const int MAX=10001;
 
struct segment
{
	int l,r;
};
 
segment S[MAX];
int N,Ans;
int F[MAX];
 
int cmp(const void *a,const void *b)
{
	return ((segment *)a)->r - ((segment *)b)->r;
}
 
void init()
{
	int i;
	freopen("rez.in","r",stdin);
	freopen("rez.out","w",stdout);
	scanf("%d",&N);
	for (i=1;i<=N;i++)
	{
		scanf("%d%d",&S[i].l,&S[i].r);
	}
	qsort(S+1,N,sizeof(S[0]),cmp);
}
 
void dynamic()
{
	int i,j;
	for (i=1;i<=N;i++)
	{
		for (j=N-1;j>=1;j--)
		{
			if (S[j].r<=S[i].l)
			{
				if (F[j]>F[i])
				{
					F[i]=F[j];
				}
			}
		}
		F[i] += S[i].r - S[i].l;
		if (F[i]>Ans)
			Ans=F[i];
	}
}
 
int main()
{
	init();
	dynamic();
	cout << Ans;
	return 0;
}