s09174. 果子合并·代价账本

题目描述

果园里有 $n$ 堆果子，第 $i$ 堆有 $a_{i}$ 个果子。每一轮可以任选两堆合并成一堆，这一轮的代价记为合并前后两堆果子个数之和；合并得到的堆可以继续参与后续合并。经过 $n - 1$ 轮合并后只剩一堆。

合并顺序可以自由选择，总代价为每一轮代价之和。请输出总代价可能达到的最小值，这本账要记得越省越好。

第一行一个整数 $n$ 。

第二行 $n$ 个整数 $a_{1}, a_{2}, \dots, a_{n}$ 。

一行一个整数，表示最小总代价。当 $n = 1$ 时无须合并，总代价为 $0$ 。

输入

5
1 2 3 4 5

输出

先合并 $1, 2$ 代价 $3$ ，再合并 $3, 3$ 代价 $6$ ，再合并 $4, 5$ 代价 $9$ ，最后合并 $6, 9$ 代价 $15$ ，总代价 $3 + 6 + 9 + 15 = 33$ ；每次都先合并当前最小的两堆。