【问题描述】
在操场上沿一直线排列着 n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆石子合并成新的一堆， 并将新的一堆石子数记为该次合并的得分。允许在第一次合并前对调一次相邻两堆石子的次序。
计算在上述条件下将n堆石子合并成一堆的最小得分和初次交换的位置。
【输入文件】
输入数据共有二行，其中，第1行是石子堆数n≤100；
第2行是顺序排列的各堆石子数（≤20），每两个数之间用空格分隔。
【输出文件】
输出合并的最小得分。
【输入输出样例】
输入：
3
2 5 1
输出：
11
分析：
<石子归并>类型题，只是改了一个可以相邻换而已
f[i][j]：从第i堆开始到第j堆石子分成两堆的最小代价
s[i][j]：从第i堆开始到第j堆石子分成k个不同的两份（1<=k<j-i+1）的最小总代价。
则我们只需枚举每次几堆一合（2<=几<=n,1堆的已经知道），和枚举这合并的堆中的方案即可。
状态方程：
【参考程序】：
#include<fstream>
using namespace std;
int f[101][101],s[101][101],a[101];
int n;
int main()
{
ifstream cin("stone.in");
ofstream cout("stone.out");
cin>>n;
for (int i=1;i<=n;i++) cin>>a[i];
int min=0x7FFFFFFF;
for (int x=1;x<=n-1;x++)
{
int t=a[x];a[x]=a[x+1];a[x+1]=t;
memset(f,127,sizeof(f));memset(s,127,sizeof(s));
for (int i=1;i<=n;i++)
{
f[i][i]=a[i];s[i][i]=0;
}
for (int len=2;len<=n;len++)
for (int i=1;i<=n-len+1;i++)
{
int j=i+len-1;
for (int k=i;k<=j-1;k++)
if (f[i][j]>f[i][k]+f[k+1][j])
{
f[i][j]=f[i][k]+f[k+1][j];
s[i][j]=f[i][j]+s[i][k]+s[k+1][j];
}
else if (f[i][j]==f[i][k]+f[k+1][j])
if (s[i][j]>f[i][j]+s[i][k]+s[k+1][j])
s[i][j]=f[i][j]+s[i][k]+s[k+1][j];
}
if (s[1][n]<min) min=s[1][n];
t=a[x];a[x]=a[x+1];a[x+1]=t;
}
cout<<min<<endl;
return 0;
}