4267. 石子合并III

【题目背景】

在省实验的操场上，排列着 $N$ 堆石子。这些石子需要通过合并操作最终变为一堆。这不仅仅是一次简单的搬运，更是一场关于最优决策的博弈。

【题目描述】

在一个操场上摆放着一排 $N$ 堆石子。现要将石子有次序地合并成一堆。
规定每次只能选相邻的 $2$ 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。
试设计一个算法，计算出将 $N$ 堆石子合并成一堆的最小总得分。

【输入格式】

第一行一个整数 $N$。
接下来 $N$ 行，第 $i$ 行一个整数 $a_i$，代表第 $i$ 堆石子的石子数。

【输出格式】

输出一个整数，表示将所有石子合并为一堆的最小得分。

【样例输入】

4
1
1
1
1

【样例输出】

8

【样例说明】

四堆石子均为 $1$。

1. 合并前两堆，得分 $2$，序列变为 $[2, 1, 1]$。 

2. 合并后两堆，得分 $2$，序列变为 $[2, 2]$。 

3. 合并剩下的两堆，得分 $4$，序列变为 $[4]$。 

总得分 = $2 + 2 + 4 = 8$。

【数据规模与约定】

对于 $100 \%$ 的数据：$N <= 40000$，$a_i <= 200$。

【来源】

SDOI 2008