网站页面
当前课程
成员
常规
第一章 分治算法
第二章 递归算法
第三章 排列组合问题
第四章 高精度算法
第五章 排序算法
第六章 穷举算法
第七章 贪心算法
第八章 递推算法
第九章 搜索算法
第十章 模拟算法
合并魔法石1
成绩 | 100 | 开启时间 | 2016年05月30日 星期一 12:25 |
折扣 | 0.8 | 折扣时间 | 2016年05月30日 星期一 12:25 |
允许迟交 | 是 | 关闭时间 | 2016年05月30日 星期一 12:25 |
输入文件 | merge1.in | 输出文件 | merge1.out |
【题目描述】合并魔法石1(merge1.cpp/c/pas)
太空梯的能量导轨上有n堆魔法石排成一排,其编号为1,2,3,…,n(n≤100)。每块魔法石有一定的数量,例如有7堆魔法石,分别为13,7,8,16,21,4,18。
现在要将n堆魔法石归并成为一堆。归并的过程为每次只能将相邻的两堆魔法石堆成一堆,这样经过n-1次归并后成为一堆,如上面的7堆魔法石,可以有多种方法归并成一堆,其中的两种方法如图所示。
则(a)的归并代价为20+24+25+44+69+87=267
(b)的归并代价为15+37+22+28+59+87=248
可见不同的过程得到的归并代价是不一样的,现在请编程找出一种合理的方法,使归并代价最小。
【输入格式】
第一行为一个整数n,且1<n≤100,表示有n堆沙子,第二行为n堆魔法石的数量。
【输出格式】
一个整数,即最小代价。
【输入样例1】
7
13 7 8 16 21 4 18
【输出样例1】
239
【输入样例2】
10
12 3 13 7 8 23 14 6 9 34
【输出样例2】
398