史萊姆(slime)是一種初級的怪物,常常是RPG遊戲裡一開始打怪的對象。由於長期被玩家所欺負,所以史萊姆們想要團結起來對抗更強大的玩家,於是史萊姆的長者提出了合體為史萊姆王的方案。合體為史萊姆王的規則如下:
1. 每次只能兩隻史萊姆合體。
2. 合體之後的攻擊力為原先兩隻史萊姆攻擊力的總和,但也要消費同樣的魔法點數。
3. 合體過後的史萊姆可以繼續和其他史萊姆合體,直到只剩下一隻史萊姆為止。
雖然合體之後的總攻擊力是一樣的,但是合體的順序卻會影響到消費的魔法點數,例如有三隻攻擊力為 1、2、3 的史萊姆要合體,如果是 1 和 2 先合體再跟 3 合體,則兩次合體消費 1+2=3、3+3=6 的魔法點數,加起來是 3+6=9 點;但如果改成 2 和 3 先合體再跟 1 合體,則兩次合體消費 2+3=5、5+1=6 的魔法點數,加起來是 5+6=11 點,比前一個方式多消費了 2 點。
現在給你一群史萊姆的攻擊力值,請問你要合體成最強大的史萊姆(也就是合體到只剩一隻),需要花費多少的魔法點數。
一開始有一個正整數 N (1<=N<=1000),代表要合體的史萊姆個數。接下來有 N 個正整數 Ai (1<=Ai<=10000),代表這 N 隻史萊姆的攻擊力值。
請輸出全部合體到只剩一隻史萊姆王,需要花費的魔法點數的最小值。
5 1 3 2 5 4
33
10 71 11 81 71 91 61 81 51 31 71
1995
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |