我看题解区关于 dp 与四边形优化的解读已经够详细了，所以就po一版代码吧，性能与性感兼得~

//
// Created by 南川 on 2021/2/21.
//


#include "cstdio"
#include "cstring"

const int N = 1000;

int main () {
    int n, v, sum[N + 1]{0}, dp[N + 1][N + 1], s[N+1][N+1];
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &v);
        sum[i] = sum[i - 1] + v;
        s[i][i] = i;
        dp[i][i] = 0;
        std::memset(dp[i]+i+1, 0x3f, sizeof(int)*(n-i));
    }

    for(int i=n-1; i; --i)
        for(int j=i+1; j<=n; ++j)
            for (int k = s[i][j-1]; k <= s[i+1][j]; ++k)
            {
                int val = dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1];
                if(val < dp[i][j]) dp[i][j] = val, s[i][j] = k;
            }

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