POI 1997 階梯教室設備利用 Lecture halls reservation
本文正體字版由OpenCC轉換
提供一個沒有優化的O(N^2)的動態規劃解法。首先對所有的演講時間區間按結束時間從小到大排序，然後設定狀態。
S[i].l和S[i].r分別表示第i個演講的開始和結束時間。 F[i]爲進行第i個演講時已經使用了的最大的時間
狀態轉移方程 F[i] = Max{ F[j] | S[j].r <=S[i].l } + S[i].r - S[i].l
結果 Max { F[i] }
#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;
}
階梯教室設備利用
【問題描述】
我們現有許多演講要在階梯教室中舉行。每一個演講都可以用唯一的起始和終止時間來確定，如果兩個演講時間有部分或全部重複，那麼它們是無法同時在階級教室中舉行的。現在我們想要盡最大可能的利用這個教室，也就是說，我們需要在這些演講中選擇一些不重複的演講來舉行使得他們用的總時間儘可能的長。我們假設在某一演講結束的瞬間我們就可以立即開始另一個演講。
任務：
請寫一個程序：
• 在輸入文件中讀入所有演講的起始和終止時間；
• 計算最大的可能演講總時間；
• 把結果寫到輸出文件中。
【輸入文件】
在輸入文件的第一行包括一個正整數 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
上次修改時間 2017-02-03