记录编号	296294	评测结果	AAAAAAAAAA
题目名称	[POI 1997] 阶梯教室设备利用	最终得分	100
用户昵称	ljt	是否通过	通过
代码语言	C++	运行时间	0.062 s
提交时间	2016-08-15 10:39:59	内存使用	2.67 MiB

#include <bits/stdc++.h>
using namespace std;

int n, dp[30005];
struct p{
        int beg, to;
        friend bool operator < (p a, p b)
        {
                return a.to < b.to;
        }
}a[10005];
int main()
{
        freopen("rez.in", "r", stdin);
        freopen("rez.out", "w", stdout);
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
                scanf("%d%d", &a[i].beg, &a[i].to);
        memset(dp, 0, sizeof dp);
        sort(a+1, a+n+1);
        int j = 1;
        for (int i = 0; i <= 30000; i++) {
                if (i > 0)
                        dp[i] = dp[i-1];
                if(j <= n)
                        while (a[j].to == i) {
                                dp[i] = max(dp[i], dp[a[j].beg]+a[j].to-a[j].beg);
                                j++;
                        }
        }
        printf("%d", dp[30000]);
        return 0;
}