內容
迷信的鄉民們把許多無辜的人送到祭壇上當祭品，你希望能拯救他們。祭壇上有 N 個人，魔鬼吃掉第 i 個人的靈魂需要 T[i] 秒，而你拯救一個人只需要 1 秒，當然你只能去救還沒被魔鬼吃掉、也沒有正在被吃的人。但你是個貪婪的人，所以你要求每個被救的人都要支付一定的報償。你估計第 i 個人能支付的報酬是 R[i]。
另外，作為祭祀負責人之一，你可以改變祭品的排列順序，魔鬼會從第一個開始吃起。
請問你最多可以拿到多少報酬呢？
輸入說明
第1行有個數字 N ，代表總祭品數。
再來的 N 行每行有兩個數字， T[i] 和 R[i]，代表吃掉第 i 個祭品所需時間以及他能給的報酬。
1 <= N <= 2000
0 <= T[i] <= 2000
1 <= R[i] <= 1000000000
底下範例說明：你把報酬少的那兩人先給魔鬼吃掉，他要花 1 + 1 = 2 秒去吃，那你就有時間拯救其餘兩人。
輸出說明
輸出第一行有一個整數，代表你能獲得的最大報酬。
範例輸入
#1
4 2 10 0 20 1 5 1 3
範例輸出
#1
30
測資資訊：
記憶體限制：
64
MB
公開 測資點#0 (14%): 1.0s , <1K
公開 測資點#1 (14%): 1.0s , <1K
公開 測資點#2 (14%): 1.0s , <1M
公開 測資點#3 (14%): 1.0s , <1M
公開 測資點#4 (14%): 1.0s , <1M
公開 測資點#5 (15%): 1.0s , <1K
公開 測資點#6 (15%): 1.0s , <1K
公開 測資點#0 (14%): 1.0s , <1K
公開 測資點#1 (14%): 1.0s , <1K
公開 測資點#2 (14%): 1.0s , <1M
公開 測資點#3 (14%): 1.0s , <1M
公開 測資點#4 (14%): 1.0s , <1M
公開 測資點#5 (15%): 1.0s , <1K
公開 測資點#6 (15%): 1.0s , <1K
提示 ：
標籤:
出處:
2012 TOI模擬賽試題第3題
[管理者：
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||