Description
在操场上沿一直线排列着
n堆石子。
n堆石子。
现要将石子有次序地合并成一堆。规定每次仅仅能选相邻的两堆石子合并成新的一堆，
并将新的一堆石子数记为该次合并的得分。同意在第一次合并前对调一次相邻两堆石子的次序。
计算在上述条件下将n堆石子合并成一堆的最小得分。
Input
输入数据共同拥有二行，当中，第1行是石子堆数n≤100；
第2行是顺序排列的各堆石子数（≤20），每两个数之间用空格分隔。
第2行是顺序排列的各堆石子数（≤20），每两个数之间用空格分隔。
Output
输出合并的最小得分。
Sample Input
3
2 5 1
Sample Output
11
Hint
Source
NOI1995
上课刚教的区间dp。对于第一次能够选择换顺序的要求，能够採用枚举交换。最后比較得出最小值就可以。
dp[ i ][ j ]表示从区间i到j合并的得分，再设置一个sum[i][j],表示i到j的总和。
#include<stdio.h>
#include<string.h>
int a[50];
int main()
{
int n,i,j,k,dp[105][105],l,len,sum[105][105],maxi=10000000,x,t,s;
int zhong;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
x=n-1;s=0;
while(x--)
{
s++;
t=a[s];
a[s]=a[s+1];
a[s+1]=t;
for(i=1;i<=n;i++)
{
dp[i][i]=0;
sum[i][i]=a[i];
for(j=i+1;j<=n;j++)
sum[i][j]=sum[i][j-1]+a[j]; //初始化sum
}
t=a[s];
a[s]=a[s+1];
a[s+1]=t;
for(i=2;i<=n;i++) //i代表区间长度，表示区间从小到大进行合并
{
for(j=1;j<=n-i+1;j++) //j表示起点
{
zhong=j+i-1; //终点
dp[j][zhong]=10000000; //初始化最大
for(k=j;k<=zhong-1;k++)
{
if(dp[j][zhong]>dp[j][k]+dp[k+1][zhong]+sum[j][zhong])
{dp[j][zhong]=dp[j][k]+dp[k+1][zhong]+sum[j][zhong];}
}
}
} if(maxi>dp[1][n])maxi=dp[1][n]; }
printf("%d\n",maxi);
}