问题 3032 --最小交换合并问题

3032: 最小交换合并问题

时间限制: 1 Sec  内存限制: 128 MB
提交: 12  解决: 11
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][36kb]

题目描述

在操场上沿一直线排列着 n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆石子合并成新的一堆, 并将新的一堆石子数记为该次合并的得分。允许在第一次合并前对调一次相邻两堆石子的次序。

    计算在上述条件下将n堆石子合并成一堆的最小得分和初次交换的位置。

输入

输入数据共有二行,其中,第1行是石子堆数n100    2行是顺序排列的各堆石子数(20),每两个数之间用空格分隔。

输出

输出合并的最小得分。

样例输入

3
2 5 1

样例输出

11

提示

来源

[提交][状态]