1149: 石子合并
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：104
解决：65
题目描述
在一个园形操场的四周摆放N堆石子（N≤100），现要将石子有次序地合并成一堆。规定
每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
编一程序，由读入堆数N及每堆的石子数（≤２０），
选择一种合并石子的方案，使得做N－1次合并，得分的总和最大；
例如，所示的４堆石子，每堆石子数（从最上面的一堆数起，顺时针数）依
次为４５９４。则３次合并得分总和最小的方案：８＋１３＋２２＝４３
得分最大的方案为：１４＋１８＋２２＝５４
每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
编一程序，由读入堆数N及每堆的石子数（≤２０），
选择一种合并石子的方案，使得做N－1次合并，得分的总和最大；
例如，所示的４堆石子，每堆石子数（从最上面的一堆数起，顺时针数）依
次为４５９４。则３次合并得分总和最小的方案：８＋１３＋２２＝４３
得分最大的方案为：１４＋１８＋２２＝５４
输入
第一行为石子堆数N；
第二行为每堆的石子数，每两个数之间用一个空格符分隔。
第二行为每堆的石子数，每两个数之间用一个空格符分隔。
输出
有两行，
第一行即得分最小的方案，最终结果
第二行得分最大的方案
样例输入 复制
4
4 5 9 4样例输出 复制
43
54