[動態規劃]OI練習題 最後的利益 9cwy 解題報告

【問題描述】
最近9C馬上就要和WY交收WOW的運營權了，9C為了最後的利益決定讓GM控制玩家上線時間。因為9C的小霸王伺服器總是容易爆滿，所以某伺服器中只剩一個玩家的位子，GM為了讓玩家在線時間總和最長。他將選擇一些上線時間不重複的玩家讓他們上線。我們假設某玩家下線以後，另一個玩家可以立即登入。但是GM又笨又懶，他希望你能幫他幫他寫一個程序來完成這個任務。

【輸入文件】

輸入文件第一行是一個正整數n，n<=10000，為玩家數量

一下n行每行含有兩個數t1、t2表示某玩家上線時段

【輸出文件】

輸出最長遊戲總時間

 

【輸入樣例】

9cwy.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

9cwy.out

16

【分析】

動態規劃。

先以每個玩家的t1、t2為關鍵字進行雙關鍵字排序。數據量不小，需要使用快速排序函數或者STL內建排序函數以及STL內建的鏈表合併函數以實現O(N*LogN)時間複雜度的排序。

狀態設定：F[i] 如果讓排序後的第i個玩家上線獲得的最大在線時間。

初始狀態：F[0]=0,F[1]=T[i]; 

狀態轉移方程：F[i]=Max{F[j]+T[i] (End[j]<=Begin[i]) } (1<=j<=i-1)

目標結果：Max{F[i]} (1<=i<=N)

【我的代碼】

裸代碼RawCode

C++语言: Codee#25585

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