再探石子合并
题目描述
题目描述
There is an old stone game.At the beginning of the game the player picks n(1≤n≤50000) piles of stones in a line. The goal is to merge the stones in one pile observing the following rules:
At each step of the game,the player can merge two adjoining piles to a new pile.The score is the number of stones in the new pile.
You are to write a program to determine the minimum of the total score.
At each step of the game,the player can merge two adjoining piles to a new pile.The score is the number of stones in the new pile.
You are to write a program to determine the minimum of the total score.
输入描述:
The input contains several test cases. The first line of each test case contains an integer n, denoting the number of piles. The following n integers describe the number of stones in each pile at the beginning of the game.
The last test case is followed by one zero.
输出描述:
For each test case output the answer on a single line.You may assume the answer will not exceed 1000000000.
示例1
输入
1 100 3 3 4 3 4 1 1 1 1 0
输出
0 17 8