b589. 超級馬拉松賽
Tags : DP
Accepted rate : 336人/354人 ( 95% ) [非即時]
評分方式:
Tolerant

最近更新 : 2015-10-21 13:28

Content

一個超級馬拉松比賽將開始。在遊戲中,選手每天需要跑不同的路徑。假設遊戲全部有 n 條路徑; 每個路徑得分可以是不同的。如果一名選手不能在規定時間內完成一條路徑,他該路徑得到零分;如果玩家完成了一條路徑在一個規定的時間,他得到該路徑設定的得分;如果玩家完成了一條路徑,用較短的時間,他可以得兩倍分數。

小愛想參加這個比賽,她如果在一條路徑上按正常速度來跑,就只能拿到原始分數,如果他加速跑,就能拿到兩倍分數,不過她就會需要在加速跑完後的下一條路徑上休息而速度變慢得到0分,請寫一個程式幫助小愛計算哪些路徑應該加速得到兩倍分數而能獲得最高的總得分。

Input

輸入資料包含多組測試資料,每一組測試資料有兩行,第一行有一個數字 n 代表有 n 條路徑要跑 1 <= n <= 40,第二行有 n 個整數代表每個路徑的原始得分 10 <= P1, P2, ... Pn <= 100 

當 n 為 0 時代表輸入結束

Output

對每一組測試資料輸出最好的總得分,每一筆資料輸出一行

Sample Input #1
1
10
2
15 10
2
30 10
3
90 60 10
3
65 50 50
3
40 60 35
0
Sample Output #1
20
35
60
210
230
170
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (100%): 10.0s , <1K
Hint :
Tags:
DP
出處:
SEARCC-ISSC國際學生程式設計競賽 [管理者: spocktsai(囧rz) ]


ID User Problem Subject Hit Post Date
26060 154535(unknown) b589
狀態轉移
552 2021-07-14 19:51