一個馬拉松比賽即將開始。在遊戲中,玩家需要每天跑一條不同的路徑。假設遊戲有N條路徑,每個路徑的得分可能會有所不同。如果一名玩家不能在一個正常的時間完成跑完路徑,他將得到零分,如果一名玩家在一個正常的時間完成跑完路徑,他將可以得到正常的分數,如果一名玩家在很短的時間內完成跑完路徑,他將得到了2倍的分數。而愛麗絲將要加入此遊戲。如果她以正常的速度去跑,她將得到正常的分數。如果她以全速去跑時,她將得到2倍的分數,但她需要好好休息一天,因此第二天她將得到零分。因為每個路徑有不同的得分分數,因此愛麗絲在某些路徑應使用全速去跑以便獲得最好的分數成績。請你幫助愛麗絲找到最好的策略,以獲得最佳的分數成績。
每筆測試資料包含兩行。第一行表示路徑數,N。第二行有N個整數。每個整數表示以正常速度跑完此路徑的得分分數;第一個整數表示的第一條路徑的得分,第二個表示第二個路徑的分數,依此類推。 而限制條件,1 <= N <= 40。所有的得分分數是10和100之間的整數。
對於每筆測試資料,輸出其最佳跑法的得分分數,而每筆輸出用換行隔開 。
1 10 2 15 10 2 30 10 3 90 60 10 3 65 50 50 3 40 65 30
20 35 60 210 230 170
動態規劃(Dynamic Programming)
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |