641. 环形石子合并
时间限制：1000 MS 内存限制：64 MB
题目描述
## 题目描述 在一个圆形操场的四周摆放了 $n$ 堆石子，现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记为该次合并的得分。 请编写一个程序，读入堆数 $n$ 及每堆的石子数，并进行如下计算：（均不超过 $10000$）， - 选择一种合并石子的方案，使得做 $n-1$ 次合并，得分的**总和最小**； - 选择一种合并石子的方案，使得做 $n-1$ 次合并，得分的**总和最大。** 例如，如图 $9.6-1$ 所示的 $4$ 堆石子，每堆石子数（从最上面的一堆开始按顺时针方向数）依次为 $4$、$5$、$9$、$4$，则 $3$ 次合并得分总和最小的方案如图 $9.6-2$ 所示，得分总和最大的方案如图 $9.6-3$所示。 ## 输入格式 第一行包含整数 $n$，表示共有 $n$ 堆石子。 第二行包含 $n$ 个整数，分别表示每堆石子的数量。 ## 输出格式 输出共两行： 第一行为合并得分总和最小值， 第二行为合并得分总和最大值。 ## 数据范围 $1 \le n \le 200$ ## 输入 ```in1 4 4 5 9 4 ``` ## 输出 ```out1 43 54 ``` ## 提示