题目描述

在一个操场上摆放着一排 $n$ 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的 $2$ 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。

试设计一个算法，计算出将 $n$ 堆石子合并成一堆的最小得分。

输入格式

第一行是一个数 $n$。

以下 $n$ 行每行一个数 $a_i$，表示石子数目。

输出格式

共一个数，即 $n$ 堆石子合并成一堆的最小得分。

4
1
1
1
1

8

数据规模与约定

对于 $100\%$ 的数据，$1 \leq n \leq 40000$，$1 \leq a_i \leq 200$。

题目来源

没有写明来源