a675:
水底機器人
Content
妮可成功進入水底機器人國際總決賽，決賽要求機器人要用電池驅動。她正為這次的其中一個重要任務作規劃。
這個任務是這樣的：機器人要從一條筆直的水道的一端開始，水道的總長度為 L 厘米。沿水道上不同的位置 ( 距離起點為 di 厘米 ) 上有些不同重量沉在水底的物件，這些物件有不同得分值 pi，妮可要做的就是把其中一些 ( 任意選擇 ) 物件拾起放在機器人的貨籃內，並把它們帶到終點。但整個運送過程受著以下實際條件的限制：
- 若能成功將物件運到終點，妮可的得分會是所有運到終點物件的分值總和
- 機器人在水底每前進 1 厘米，就需要使用 1 + nt 單位的電力，其中 nt 是機器人在這 1 厘米運行時所負載的物件的總數目
- 在開始時，機器人的電池共有 P 個單位的電力
- 若在未到達終點前電力耗盡，則任務失敗而得不到任何分數。若到達終點時電力剛好耗盡或有餘，則任務都算是成功，可以得到應有的分數
- 假設妮可的機器人的載貨籃是可以把所有的物件都裝下
現在比賽大會已公佈了每件物件的位置及其得分值 ( 所有這些數值均為正整數 )。妮可要做的就是估算一下她最多可以得到多少分？
Input
輸入的第一行有三個正整數 L, P, N，分別代表水道的總長度，電池最初的電量以及物件的總數。( 100 <= L <= 1000000, L <= P <= 20000000, 1 <= N <= 30 )
隨後的 N 行上，每行有一對正數 di 及 pi，代表第 i 件物件與起點的距離及其得分值，其中 0 < di < L 而 1 <= pi <= 100
Output
輸出資料應只含有一個整數，它代表兩個輸入整數的和。
Sample Input
#1
100 110 4 1 100 96 7 95 5 98 4
Sample Output
#1
12
測資資訊：
記憶體限制：
64
MB
不公開 測資點#0 (10%): 1.0s , <1K
不公開 測資點#1 (10%): 1.0s , <1K
不公開 測資點#2 (10%): 1.0s , <1K
不公開 測資點#3 (10%): 1.0s , <1K
不公開 測資點#4 (10%): 1.0s , <1K
不公開 測資點#5 (10%): 1.0s , <1K
不公開 測資點#6 (10%): 1.0s , <1K
不公開 測資點#7 (10%): 1.0s , <1K
不公開 測資點#8 (10%): 1.0s , <1K
不公開 測資點#9 (10%): 1.0s , <1K
不公開 測資點#0 (10%): 1.0s , <1K
不公開 測資點#1 (10%): 1.0s , <1K
不公開 測資點#2 (10%): 1.0s , <1K
不公開 測資點#3 (10%): 1.0s , <1K
不公開 測資點#4 (10%): 1.0s , <1K
不公開 測資點#5 (10%): 1.0s , <1K
不公開 測資點#6 (10%): 1.0s , <1K
不公開 測資點#7 (10%): 1.0s , <1K
不公開 測資點#8 (10%): 1.0s , <1K
不公開 測資點#9 (10%): 1.0s , <1K
Hint ：
#非官方測試數據
Tags:
出處:
MOI 2018
[管理者：
]
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||