dp的石子合并+前缀和

#include <iostream>

using namespace std;
const int N = 1010;
int s[N];
int f[N][N];//表示f[i][j] i->j合并的最小代价
int n;

int main(){
    cin >> n;
    for(int i = 1;i <= n;i++){
        int x;
        cin >> x;
        s[i] = s[i - 1] + x;
    }

    for(int len = 2;len <= n;len++){
        for(int j = 1;j + len - 1 <= n;j++){
            int l = j,r = j + len - 1;
            f[l][r] = 1e9;
            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;
}