d001: 馬拉松比賽
標籤 :
通過比率 : 0人/0人 (0%) [非即時]
評分方式:
Tolerant

最近更新 : 2022-02-25 11:03

內容

一個馬拉松比賽即將開始。在遊戲中,玩家需要每天跑一條不同的路徑。假設遊戲有N條路徑,每個路徑的得分可能會有所不同。如果一名玩家不能在一個正常的時間完成跑完路徑,他將得到零分,如果一名玩家在一個正常的時間完成跑完路徑,他將可以得到正常的分數,如果一名玩家在很短的時間內完成跑完路徑,他將得到了2倍的分數。而愛麗絲將要加入此遊戲。如果她以正常的速度去跑,她將得到正常的分數。如果她以全速去跑時,她將得到2倍的分數,但她需要好好休息一天,因此第二天她將得到零分。因為每個路徑有不同的得分分數,因此愛麗絲在某些路徑應使用全速去跑以便獲得最好的分數成績。請你幫助愛麗絲找到最好的策略,以獲得最佳的分數成績。

輸入說明

每筆測試資料包含兩行。第一行表示路徑數,N。第二行有N個整數。每個整數表示以正常速度跑完此路徑的得分分數;第一個整數表示的第一條路徑的得分,第二個表示第二個路徑的分數,依此類推。 而限制條件,1 <= N <= 40。所有的得分分數是10和100之間的整數。

輸出說明

對於每筆測試資料,輸出其最佳跑法的得分分數,而每筆輸出用換行隔開 。

範例輸入 #1
1
10
2
15 10
2
30 10
3
90 60 10
3
65 50 50
3
40 65 30
範例輸出 #1
20
35
60
210
230
170
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (50%): 1.0s , <1K
公開 測資點#1 (50%): 1.0s , <1K
提示 :

動態規劃(Dynamic Programming)

標籤:
出處:
2010 ISSC 第5次模擬賽第5題 [管理者:
franklin (管理員)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」