描述
有n堆石子排成一条直线，每堆石子有一定的重量。现在要合并这些石子成为一堆石子，但是每次只能合并相邻的两堆。每次合并需要消耗一定的体力，该体力为所合并的两堆石子的重量之和。问最少需要多少体力才能将n堆石子合并成一堆石子？
输入
输入只包含若干组数据。每组数据第一行包含一个正整数n(2<=n<=100)，表示有n堆石子。接下来一行包含n个正整数a1,a2,a3,...,an（0<ai<=100，1<=i<=n）。
输出
对应输入的数据，每行输出消耗的体力。
样例输入
2
47 95
样例输出
142
思路：
s[i]表示前i堆石头的数量总和，f[i][j]表示把第i堆到第j堆的石头合并成一堆的最小值，状态转移方程如下：
for(int i=n-1;i>=1;i--) for(int j=i+1;j<=n;j++) for(int k=i;k<=j-1;k++) f[i][j] = min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
例如当输入
4
1 1 1 1时
最终得到答案f[1][4] = 8
当你不懂的时候，动笔总是没错的~
1 #include<bits/stdc++.h> 2 using namespace std; 3 int f[101][101],s[101]; 4 int main() 5 { 6 int n; 7 while(cin>>n) 8 { 9 for(int i=1;i<=n;i++) 10 { 11 int x;cin>>x; 12 s[i] = s[i-1]+x;//记录前i个石子的总和 13 } 14 memset(f,127/3,sizeof(f)); //初始化为较大但是又没那么大的数 15 for(int i=1;i<=n;i++)f[i][i] = 0; //从第i堆到第i堆的得分应该是0 16 for(int i=n-1;i>=1;i--) 17 for(int j=i+1;j<=n;j++) 18 for(int k=i;k<=j-1;k++) 19 f[i][j] = min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]); 20 cout<<f[1][n]<<endl; 21 } 22 return 0; 23 }