a567. 死線排程
Tags :
Accepted rate : 240人/288人 ( 83% ) [非即時]
評分方式:
Tolerant

最近更新 : 2012-11-25 00:13

Content
 死線排程

Background

大學最常遇見的就是死線(deadline),死線的選擇常常是大學生的煩惱,如何得到最大利益的排程?

 

The Problem

給 N 個作業,每個作業分別有 deadline 與 profit,在此分別以 di與pi 表示之,台灣的大學生很厲害每項作業都可以在一天的時間內完成,同時也很偷懶,最喜歡在最後一天才開始寫作業,意即在最後一天完成作業是可接受的。

 

現在是日期的第一天,請你安排他的工作。

 

Input

多筆測資

每組第一行有一個數字 N 代表作業總數,
接下來有 N 行資料,每行上有兩個數字 di 與 pi

0 < N ≦ 10000, 0 < di ≦ 10000, 0 < pi <32767

Output
排程方法數可能很多,輸出最大獲益即可。
Sample Input #1
6
2 5
3 6
4 4
4 2
5 3
5 1
8
7 1
7 1
7 1
10 1
11 1
9 1
10 1
11 1
Sample Output #1
20
8
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <10M
Hint :

小光偷看了一下 偷懶學生的排程。

範例測資一

Day

1

2

3

4

5

Task

4

1

2

3

5

範例測資二

Day

1

2

3

4

5

6

7

8

9

10

11

Task

X

X

X

8

3

2

1

7

6

4

5

 

測資不嚴謹、描述不清、題目類型重覆,感謝您的通知。

 

Tags:
出處:
I2A [管理者: morris1028 (碼畜) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
24870 fire5386 (becaidorz) a567
1044 2021-04-02 16:02
24867 allllllan123 ... (God of Computer...) a567
Greedy 證明
1163 2021-04-02 15:29