POI1997 階梯教室設備利用 rez 解題報告

階梯教室設備利用

【問題描述】

我們現有許多演講要在階梯教室中舉行。每一個演講都可以用唯一的起始和終止時間來確定，如果兩個演講時間有部分或全部重複，那麼它們是無法同時在階級教室中舉行的。現在我們想要盡最大可能的利用這個教室，也就是說，我們需要在這些演講中選擇一些不重複的演講來舉行使得他們用的總時間儘可能的長。我們假設在某一演講結束的瞬間我們就可以立即開始另一個演講。

任務：

請寫一個程序：

• 在輸入文件中讀入所有演講的起始和終止時間；

• 計算最大的可能演講總時間；

• 把結果寫到輸出文件中。

【輸入文件】

在輸入文件的第一行包括一個正整數 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

16 

【分析】

做完USACO Nov07 Silver的Milking Time（擠奶時間,milkprod）這題後，會發現本題十分簡單。

具體做法在這不多說了，可以看看我寫milkprod那道題的解題報告。

【我的代碼】

裸代碼RawCode

C++语言: Codee#25366

01 /*
02 *Problem:POI 1997 rez
03 *Author: Yee-fan Zhu
04 *Email: zyfworks@gmail.com
05 */
06 #include <iostream>
07 #include <cstdio>
08 #include <cstdlib>
09 using namespace std;
10
11 int N;
12 class REZ
13 {
14 public:
15     int s,e,t;
16 }Rez[10001];
17 int F[10001];
18
19 int MAX(int a,int b)
20 {
21     return (a>b?a:b);
22 }
23
24 int cmp(const void *a,const void *b)
25 {
26     class REZ *c=(class REZ *)a;
27     class REZ *d=(class REZ *)b;
28     return c->s-d->s;
29 }
30
31 void init()
32 {
33     scanf("%d\n",&N);
34     for (int i=1;i<=N;i++)
35     {
36         scanf("%d %d\n",&Rez[i].s,&Rez[i].e);
37         Rez[i].t=Rez[i].e-Rez[i].s;
38     }
39     qsort(Rez+1,N,sizeof(REZ),cmp);
40 }
41
42 void dynamic()
43 {
44     int Ans=0;
45     F[0]=0;
46     for(int i=1;i<=N;i++)
47     {
48         int Max=0;
49         for(int j=1;j<=i-1;j++)
50         {
51             if(Rez[j].e<=Rez[i].s)
52                 Max=MAX(Max,F[j]);
53         }
54         F[i]=Max+Rez[i].t;
55         Ans=MAX(Ans,F[i]);
56     }
57     printf("%d\n",Ans); 
58 }
59
60 int main()
61 {
62     freopen("rez.in","r",stdin);
63     freopen("rez.out","w",stdout);
64     init();
65     dynamic();
66     return 0;
67 }