题意分析

每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。
每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。

状态表示:f[i][j]：从第i堆到第j堆石子合并为一堆的最小代价。
那么状态应该怎么去进行计算，众所周知，石子应该是两堆进行合并的，那么有人说了，你是从i到j堆不符合，是怎么计算的。 这时，我们可以去引入区间这个变量，区间从2开始，也就是两堆石子，一直到n，虽然我们的区间是从小到大进行计算的，但是我们在进行下一次变量的计算时，上一次的变量已经被计算出来，并且不会被覆盖，所以成立。

状态方程：f[l][r] =f[l][k] +f[k+1][r] + l~r堆的总质量(可以用前缀和进行) ，k为区间[l,r]的分割点。

#include<iostream>
#include<algorithm>

using namespace std;

const int N=310;
int n;
int s[N];
int f[N][N];

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)  scanf("%d",&s[i]);

    for(int i=1;i<=n;i++)  s[i]+=s[i-1];   //前缀和

    for(int len=2;len<=n;len++)    //区间长度
       for(int i=1;i+len-1<=n;i++)  //枚举起点
       {
           int l=i,r=i+len-1;     //r为区间终点
           f[l][r]=1e8;
           for(int k=l;k<r;k++)  //枚举分割点。
             f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
       }
       cout<<f[1][n]<<endl;
       return 0;
}