b589. 超級馬拉松賽
標籤 : DP
通過比率 : 422人/445人 ( 95% ) [非即時]
評分方式:
Tolerant

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

內容

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

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

輸入說明

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

當 n 為 0 時代表輸入結束

輸出說明

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

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

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
42843 chiuliyou@gm ... (邱立宇) b589
動態規劃五步法
71 2024-10-08 00:58