题目名称	33. [POI 1997] 阶梯教室设备利用
输入输出	`rez.in/out`
难度等级	★★
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	10
题目来源	cqw 于2008-04-24加入
开放分组	全部用户
提交状态
分类标签	动态规划决策单调性优化
	分享题解

通过：204，提交：436，通过率：46.79%
Youngsc	100	0.000 s	0.00 MiB	C++
Evolt	100	0.000 s	0.00 MiB	C++
Ryper	100	0.000 s	0.00 MiB	C++
1020	100	0.000 s	0.00 MiB	C++
小e	100	0.011 s	4.50 MiB	C++
soler	100	0.013 s	0.40 MiB	C++
soler	100	0.013 s	0.44 MiB	C++
soler	100	0.013 s	0.44 MiB	C++
Faller	100	0.013 s	0.47 MiB	C++
求魔	100	0.013 s	1.86 MiB	C++

本题关联比赛
2008haoi模拟训练3

关于阶梯教室设备利用的近10条评论(全部评论)
dp[l] = max(dp[l-1], dp[beg[j]]+to[j]-beg[j]) if to[j] == l dp[l] = dp[l-1] else 很好理解的方程，优化。。只需要将数据按照to由小到大排序，然后决策就单调了，然后就没有然后了排序是O(nlgn)，后面是摊还O(n)，总共O(nlgn) 用hash或者邻接表可以到O(n)。 ljt 2016-08-15 11:16 8楼
细节啊 521 2016-06-07 23:40 7楼
为什么O(n^2)的算法也可以过。。。。不科学 HouJikan 2014-08-23 12:42 6楼
直接动规，果断慢成翔 Frost 2013-12-03 21:01 5楼
为什么n^2跑了0.4s多。。是评测机卡了么- -还是 sort太慢？馒头 2013-10-30 14:02 4楼
线段的权值并非其长度，而是长度-1（因为有重叠） cstdio 2013-04-10 16:13 3楼
函数好慢…… yanzheng 2009-09-16 17:43 2楼
POI1997的题，好像还是山东的省选 BYVoid 2008-11-28 19:33 1楼

33. [POI 1997] 阶梯教室设备利用

★★ 输入文件：rez.in 输出文件：rez.out 简单对比
时间限制：1 s 内存限制：128 MiB

【问题描述】

我们现有许多演讲要在阶梯教室中举行。每一个演讲都可以用唯一的起始和终止时间来确定，如果两个演讲时间有部分或全部重复，那么它们是无法同时在阶级教室中举行的。现在我们想要尽最大可能的利用这个教室，也就是说，我们需要在这些演讲中选择一些不重复的演讲来举行使得他们用的总时间尽可能的长。我们假设在某一演讲结束的瞬间我们就可以立即开始另一个演讲。

任务：

请写一个程序：

• 在输入文件中读入所有演讲的起始和终止时间；

• 计算最大的可能演讲总时间；

• 把结果写到输出文件中。

【输入文件】

在输入文件的第一行包括一个正整数 n ， n <= 10000 ，为所有的演讲的数目。

以下的 n 行每行含有两个由空格隔开整数 p 和 k ， 0 <= p < k <= 30000 。这样的一对整数表示一个演讲由时间 p 开始到时间 k 结束。

【输出文件】

输出文件只有唯一的一个整数，为最长的演讲总时间。

【样例输入】

rez.in

12
1 2
3 5
0 4
6 8
7 13
4 6
9 10
9 12
11 14
15 19
14 16
18 20

【样例输出】

rez.out