用的区间 dp

#include <bits/stdc++.h>
#define maxn 310
using namespace std;

int n;
int m[maxn];
int f[maxn][maxn]; // f[i][j]表示合并区间(i, j)所有石子所能产生的最小总代价

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

    for (int i = 1; i <= n; i++)
    {
        for (int j = i; j <= n; j++)
        {
            f[i][j] = f[i][j - 1] + m[j];
        }
    }

    for (int L = 1; L < n; L++)
    {
        for (int i = 1; i + L <= n; i++)
        {
            int j = i + L, &fij = f[i][j];
            fij = 2e9;
            for (int k = i; k < j; k++)
            {
                fij = min(fij, f[i][k] + f[k + 1][j]);
            }
            fij += f[i][j];
        }
    }

    printf("%d", f[1][n]);

    return 0;
}

输出刚好是样例的两倍