Pku1738 An old Stone Game

题目描述

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="" one="" pile="" observing="" following="" rules:="" at="" each="" step="" game,the="" player="" can="" two="" adjoining="" new="" pile.the="" score="" number="" pile.="" you="" are="" write="" program="" determine="" minimum="" total="" score.="" 就是最简单的石子合并问题.<="" p="">

---

输入格式

The input contains several test cases. The first line of each test case contains an integer n(N等于100) 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
100
3
3 4 3
4
1 1 1 1
0

---

样例输出

0
17
8

---

提示

没有写明提示

---

题目来源

LTC男人八题系列