问题 A: 圣剑plus

问题 A: 圣剑plus

时间限制: 1 Sec  内存限制: 128 MB
提交: 967  解决: 164
[状态] [讨论版] [提交] [命题人:]
题目描述
精灵勇者yzh的圣剑被魔王打成了碎片,但是精灵勇者yzh可以消耗精灵能量来修复圣剑,并且强化成圣剑plus版本。为了保留足够的精灵能量去对付魔王,所以精灵勇者yzh要消耗尽可能少的能量。圣剑碎片每一块的重量不同,例如将重量为3和重量为5的圣剑碎片修复要消耗8点能量,你的任务是设计合理的修复次序,使精灵勇者yzhjj消耗的能量最少,并输出最少消耗的能量值
输入
共两行。
第一行是一个整数n(1≤n≤200) ,表示圣剑碎片的个数。
第二行包含 n个整数,用空格分隔,第 i个整数 (1 <= ai  <= 2000)是第 i个圣剑碎片的重量。

输出
一个整数,也就是修复圣剑所花费最少的能量。
样例输入 Copy
3
1 2 6
样例输出 Copy
12
提示
对于样例我们按照以下方案修复:
    合并1,2碎片,消耗3点能量。此时碎片为3,6.
    合并3,6碎片,消耗9点能量。此时碎片为9。
    总花费为3+9=12点。 可以证明没有比12更少的花费。