很明显的区间DP,从小状态滚到大状态就好了。
代码用了四边形不等式优化。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define gc getchar()
using namespace std;
const int N=305;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int sum[N],f[N][N],g[N][N];
int main()
{
    int n;qr(n);memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;i++)qr(sum[i]),f[i][i]=0,sum[i]+=sum[i-1],g[i][i]=i;
    for(int k=2;k<=n;k++)
        for(int l=1;l<=n-k+1;l++)
        {
            int r=l+k-1;
            for(int mid=g[l][r-1];mid<=g[l+1][r];mid++)
                if(f[l][r]>f[l][mid]+f[mid+1][r]+sum[r]-sum[l-1])
                    f[l][r]=f[l][mid]+f[mid+1][r]+sum[r]-sum[l-1],g[l][r]=mid;
        }
    qw(f[1][n]);puts("");
    return 0;
}