区间dp
#include<iostream>
using namespace std;
const int N=310;
int a[N],f[N][N];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) a[i]+=a[i-1];
for(int len=2;len<=n;len++){ //len=1,相当于本身,f[i][i]=0;所以不需考虑
for(int i=1;i+len-1<=n;i++){
int l=i,r=i+len-1;
f[l][r]=1e8;
for(int k=l;k<r;k++)//k范围l.....r-1
f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+a[r]-a[l-1]);
}
}
cout<<f[1][n];
return 0;
}