#4658. 合并麦子*(2021年10月STEMA选拔赛)

合并麦子*(2021年10月STEMA选拔赛)

编程实现:合并麦子

题目描述:

秋天是个收获的季节,收获“成熟”的季节,收获“金色”的季节。农民伯伯开始收麦子了,为了省力农民伯伯每收割一部分麦子都会堆放一堆,然后再将所有堆放的麦子按照两两合并的规则合并成一大堆,依此类推,最后运回家。

合并规则如下:

  1. 每次只能将两堆麦子合成一堆;
    
  2. 每次合并麦子都会消耗体力,所消耗的体力为每次所合并的两堆麦子重量之和。
    

在给出麦子初始的总堆数及每堆麦子的重量,按照合并规则将每堆麦子两两合并,最后合成一堆,并使最后所消耗的体力最少。 (不考虑每堆麦子之间的距离等因素)

如:麦子的初始总堆数为3,每堆麦子重量分别为1,2,4,按照合并规则有三种方案:

image

第一种:将重量为1和2的麦子合并,合并出新的一堆麦子,其重量为3,消耗体力为3;再将新合并重量为3的一堆麦子和原来重量为4的一堆麦子合并,合并出新的一堆麦子,重量为7,消耗体力为7。故两次合并共消耗体力3+7=10; 第二种:将重量为1和4的麦子合并,合并出新的一堆麦子,其重量为5,消耗体力为5,再将新合并重量为5的一堆麦子和原来重量为2的一堆麦子合并,合并出新的一堆麦子,重量为7,消耗体力为7。故两次合并共消耗体力5+7=12 image 第三种:将重量为2和4的麦子合并,合并出新的一堆麦子,其重量为6,消耗体力为6,再将新合并重量为6的一堆麦子和原来重量为1的一堆麦子合并,合并出新的一堆麦子,重量为7,消耗体力为7。故两次合并共消耗体力6+7=13; image 根据要求使得最后所消耗的体力最少,所以选择第一种方案,故最少消耗体力为10。

​输入描述:​第一行输入一个正整数n(2<n<1000),表示麦子的总堆数

第二行输入n个正整数表示每堆麦子的重量(重量也表示所要消耗的体力,0<正整数<10^5^),正整数之间以一个空格隔开

​输出描述:​输出一个正整数表示按照合并规则对n堆麦子合并,得到最少消耗体力值

​样例输入:​3

1 6 2

​样例输出:​12

评分标准: (下列各评分项单独计分,得分累加;共 35 个计分点)

7分:能正确输出一组数据;

7分:能正确输出两组数据;

7分:能正确输出三组数据;

7分:能正确输出四组数据;

7分:能正确输出五组数据。

Limitation

1s, 1024KiB for each test case.