石子合并

#include<limits>
using namespace std;
const int N = 1e3;
int a[N];
int f[N][N];//f[i][j]表示的是将[i,j]区间所有石子合并成一堆所用代价最小集合
int main()
{
    int n;
    cin >>n;
    for(int i = 1; i <= n; i ++)
    {
      cin >>a[i];
      a[i] += a[i - 1];
    }
    for(int l = 2; l <= n; l ++)
    for(int i = 1; i + l - 1 <= n; i ++)
    {
        int j = l + i - 1; 
        f[i][j] = 1e8;
        for(int k = i; k < j; k ++)//[i,k],[k + 1, j]区间
        {
            f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + a[j] - a[i - 1]);
        }
    }
    cout << f[1][n];
}