最优合并代价

题目描述

有 n 个正整数。每次可以选择其中两个数 a、b，将它们合并成一个新数 a+b，本次合并的代价也是 a+b。

不断进行合并，直到只剩下一个数。请计算能够得到的最小总代价。

输入格式

第一行一个整数 n。

第二行包含 n 个正整数，表示各个数的初始权值。

输出格式

输出一个整数，表示最小总代价。

4
5 7 10 15

71

数据范围

• 1 <= n <= 100000
• 1 <= 权值 <= 10^9
• 答案可能超过 32 位有符号整数范围