1． 最小代价子母树

设有一排数，共ｎ个，例如：22 14 7 13 26 15 11。任意2个相邻的数可以进行归并，归并的代价为该两个数的和,经过不断的归并，最后归为一堆，而全部归并代价的和称为总代价，给出一种归并算法，使总代价为最小。

输入、输出数据格式与“石子合并”相同。

Sample Input

4

12 5 16 4

Sample Output

－１２ －５ １６ ４

１７ －１６ －４

－１７ －２０

３７

#include<iostream.h>
void main()
{
int a[101];
int m[101][101];
int n,i,j,k,min;
cin>>n;
for(i=0;i<n;i++)
{
cin>>a[i];
}
for(i=0;i<n;n--)
{
for(j=0;j<n;j++)
{
m[j][j+1]=a[j]+a[j+1];
}
min=m[0][1];
for(j=0;j<n-1;j++)
{
if(min>m[j][j+1])
min=m[j][j+1];
}
for(j=0;j<n;j++)
{
if(min==m[j][j+1])
{
a[j]=-1*a[j];
a[j+1]=-1*a[j+1];
if(n==1)
{
cout<<-1*a[0]<<" ";
}
else
{
for(k=0;k<n;k++)
cout<<a[k]<<" ";
}
a[j]=min;
for(k=j+1;k<n;k++)
a[k]=a[k+1];
break;
}
}
cout<<endl;
for(j=0;j<n;j++)
{
m[j][j+1]=0;
}
}
}