4263. 石子合并II

【题目背景】

在一个省实验的操场上，有 $n$ 堆石子排成一个圆圈。由于石子占据了操场的一部分，现在需要将这些石子合并成一堆。

【题目描述】

所有的石子围成一个环，每堆石子有一定的质量。合并规则如下：
1. 每次只能合并相邻的两堆石子。
2. 合并后的新石子堆质量为两堆石子质量之和。
3. 每次合并所需的代价为这两堆石子的质量总和。
你需要设计一个算法，计算出将 $n$ 堆石子合并成一堆所需的最小总代价。

【输入格式】

输入包含两行：
第一行包含一个整数 $n$，表示石子的堆数。
第二行包含 $n$ 个整数，按顺时针顺序给出每堆石子的质量 $a_i$。

【输出格式】

输出一个整数，表示合并成一堆的最小总代价。

【样例输入】

4
4 5 9 4

【样例输出】

43

【样例说明】

这是一个环形结构，四堆石子质量分别为 $4, 5, 9, 4$。 最优合并方案如下： 

1. 合并 $4$ 和 $4$（两端相邻），代价为 $8$，序列变为 $[8, 5, 9]$。 

2. 合并 $8$ 和 $5$，代价为 $13$，序列变为 $[13, 9]$。 

3. 合并 $13$ 和 $9$，代价为 $22$，序列变为 $[22]$。 

总代价 = $8 + 13 + 22 = 43$。

【数据规模与约定】

对于 $100 \%$ 的数据：$n <= 1000$，每堆石子质量 $1 <= a_i <= 10^5$。

【来源】

To_Carpe_Diem