d075: Q-6-10. 置物櫃出租 (APCS201810)
Tags : DP
Accepted rate : 0人/0人 (0%) [非即時]
評分方式:
Tolerant

最近更新 : 2020-09-23 21:31

Content

王老先生有一個置物櫃,共有 M 個相同大小的格子,置物櫃目前已經租給 n 個客戶,

第 i 位客戶所租的大小為 f(i)個格子(1 <= i <= n)。目前的承租量總和不超過 M,

但是現在王老先生自己需要使用 S 個格子的置物櫃,如果剩下的容量不夠,就必須退

掉某些客戶的租約。假設每個客戶所租容量只能全退或全不退,而退租第 i 個客戶損

失的利益與其所租容量 f(i)相同,請寫一支程式計算王老先生最小的損失利益,如

果不須退租,則損失為 0。

Input

測試資料有兩行,第一行有三個正整數,依序是 n、M 與 S,其中 S <= M,

第二行是 n 個正整數 f(1), f(2), f(3), ..., f(n),同一行的數字間以空白

隔開。1 <= n <= 100,M <= 2e5。

Output

輸出王老先生最小的損失利益。

Sample Input
// 1
3 10 6
4 4 1
// 2
5 20 14
8 2 7 2 1
Sample Output
// 1
5
// 2
15
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <1K
公開 測資點#3 (20%): 1.0s , <1K
公開 測資點#4 (20%): 1.0s , <1K
Hint :
Tags:
DP
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\mathtt{Computer}\mathsf{Information}\mathit{Club}$)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」