第一课堂
Current course
Participants
General
Topic 2
Topic 3
Topic 4
Topic 5
Topic 6
Topic 7
Topic 8
Topic 9
Topic 10
Topic 11
Topic 12
Topic 13
Topic 14
Topic 15
Topic 16
Topic 17
Topic 18
Topic 19
Topic 20
石子归并
Grade | 0 | Open Time | Tuesday, 15 January 2013, 3:55 pm |
Discount | 0.8 | Time Discount | Tuesday, 15 January 2013, 3:55 pm |
Allow late | Yes | Close Time | Tuesday, 15 January 2013, 3:55 pm |
Input file | shizi.in | Output file | shizi.out |
设有N堆沙子排成一排,其编号为1,2,3,…,N(N<=100)。每堆沙子有一定的数量。现要将N堆沙子并成为一堆。归并的过程只能每次将相邻的两堆沙子堆成一堆(每次合并花费的代价为当前两堆沙子的总数量),这样经过N-1次归并后成为一堆,归并的总代价为每次合并花费的代价和。找出一种合理的归并方法,使总的代价最小。
例如:有3堆沙子,数量分别为13,7,8,有两种合并方案,
第一种方案:先合并1,2号堆,合并后的新堆沙子数量为20,本次合并代价为20,再拿新堆与第3堆沙子合并,合并后的沙子数量为28,本次合并代价为28,将3堆沙子合并到一起的总代价为第一次合并代价20加上第二次合并代价28,即48;
第二种方案:先合并2,3号堆,合并后的新堆沙子数量为15,本次合并代价为15,再拿新堆与第1堆沙子合并,合并后的沙子数量为28,本次合并代价为28,将3堆沙子合并到一起的总代价为第一次合并代价15加上第二次合并代价28,即43;
采用第二种方案可取得最小总代价,值为43。
【输入格式】
输入由若干行组成,第一行有一个整数,n(1≤n≤100);表示沙子堆数。第2至n+1行是每堆沙子的数量。
【输出格式】
一个整数,归并的最小代价。
【输入样例】
输入文件名:shizi.in
7
13
7
8
16
21
4
18
【输出样例】
输出文件名:shizi.out
239