#4658. 合并麦子*(2021年10月STEMA选拔赛)
合并麦子*(2021年10月STEMA选拔赛)
编程实现:合并麦子
题目描述:
秋天是个收获的季节,收获“成熟”的季节,收获“金色”的季节。农民伯伯开始收麦子了,为了省力农民伯伯每收割一部分麦子都会堆放一堆,然后再将所有堆放的麦子按照两两合并的规则合并成一大堆,依此类推,最后运回家。
合并规则如下:
-
每次只能将两堆麦子合成一堆;
-
每次合并麦子都会消耗体力,所消耗的体力为每次所合并的两堆麦子重量之和。
在给出麦子初始的总堆数及每堆麦子的重量,按照合并规则将每堆麦子两两合并,最后合成一堆,并使最后所消耗的体力最少。 (不考虑每堆麦子之间的距离等因素)
如:麦子的初始总堆数为3,每堆麦子重量分别为1,2,4,按照合并规则有三种方案:
第一种:将重量为1和2的麦子合并,合并出新的一堆麦子,其重量为3,消耗体力为3;再将新合并重量为3的一堆麦子和原来重量为4的一堆麦子合并,合并出新的一堆麦子,重量为7,消耗体力为7。故两次合并共消耗体力3+7=10;
第二种:将重量为1和4的麦子合并,合并出新的一堆麦子,其重量为5,消耗体力为5,再将新合并重量为5的一堆麦子和原来重量为2的一堆麦子合并,合并出新的一堆麦子,重量为7,消耗体力为7。故两次合并共消耗体力5+7=12
第三种:将重量为2和4的麦子合并,合并出新的一堆麦子,其重量为6,消耗体力为6,再将新合并重量为6的一堆麦子和原来重量为1的一堆麦子合并,合并出新的一堆麦子,重量为7,消耗体力为7。故两次合并共消耗体力6+7=13;
根据要求使得最后所消耗的体力最少,所以选择第一种方案,故最少消耗体力为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.