回分類題庫
b036: 史萊姆王
關鍵字: 貪婪演算法-最小總花費

測資點 : 5 | Time Limit : 1000 ms | Memory Limit : 32000 KB
Accepted : 753 Times / 615 Users | Submit : 1294 Times / 646 Users | Accepted rate : 95%
題目加入時間 : 2011-11-07 11:22

Content: 简体中文

史萊姆(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 點。

現在給你一群史萊姆的攻擊力值,請問你要合體成最強大的史萊姆(也就是合體到只剩一隻),需要花費多少的魔法點數。

Input:

一開始有一個正整數 N (1<=N<=1000),代表要合體的史萊姆個數。接下來有 N 個正整數 Ai (1<=Ai<=10000),代表這 N 隻史萊姆的攻擊力值。

Output:

請輸出全部合體到只剩一隻史萊姆王,需要花費的魔法點數的最小值。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
輸入1:
5 1 3 2 5 4

輸入2:
10 71 11 81 71 91 61 81 51 31 71

Sample Output :

輸出1:
33

輸出2:
1995

Hint :

Author :

貪婪演算法-最小總花費 (管理員:sagit)

  Solve it!   Status Forum