问题说明

Gold King最近有些飘，走路都是悬浮的，一不留神，就翻了个跟头，来了个狗啃泥，翻起身一看，有一块小石头，突兀的在小路中间半掩着，Gold King费力地刨出来，发现还挺扁的，就拿起来往湖里扔，这石头在水里漂了好几下，才不甘心的沉到水里，这下可把Gold King乐坏了，觉得这挺有意思的，于是又扔了几次，越玩越有意思，可是石头没了。
Gold King想起附近有一个地方有石头，但是分成了n堆，Gold King想把它们合在一堆都搬过来，因为还要省些力用来打水漂呢，合的过程只能每次将相邻的两堆石子堆成一堆，每次合并花费的力气为这两堆石子的和，求出合并成一堆的总力气的最小值（如果只有一堆，那当然不用合并，那花费就是0）

输入格式

输入一个整数n，表示有n堆石子，
接下来输入这n个石子堆数量。

输出格式

输出对应总力气的最小值

5
1 2 3 4 5

33

提示

1<=n<=900
1<=每堆石子数<=100

来源/分类

算法培训-15-区间动态规划