问题 1018 --堆石子

1018: 堆石子

时间限制: 1 Sec  内存限制: 128 MB
提交: 409  解决: 209
[提交][状态][讨论版]

题目描述

在一个圆形操场的四周摆放着 n堆石子。 现要将石子有次序地合并成一堆。 规定每次选2 堆石子合并成新的一堆,合并的费用为新的一堆石子数。试设计一个算法,计算出将 n堆石子合并成一堆的最小总费用。

输入

输入数据第1行有1个正整数 n1n1000),表示有 n堆石子,每次选2堆石子合并。第2行有 n个整数, 分别表示每堆石子的个数(每堆石子的取值范围为[1,1000]) 。

输出

数据输出为一行, 表示对应输入的最小总费用。

样例输入

7
45 13 12 16 9 5 22

样例输出

313

提示


 中南大学计算机&软件复试QQ群373377802

来源

[提交][状态]