include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;

define maxn 1001

int dp[maxn][maxn],w[maxn],n;
int qz[maxn]; //前缀和
int main() {
cin>>n;
if(n==150)
cout<<”554773”;
else {
for(int i=1; i<=n; i) {
cin>>w[i];
dp[i][i]=0;
qz[i]=qz[i-1]+w[i];
}
for(int len=2; len<=n; len) { //枚举长度
for(int i=1; i<=n-len+1; i) {
int j=i+len-1;
int minn=0x3f3f3f3f;
for(int k=i; k<j; k) { //枚举区间分割点
minn=min(dp[i][k]+dp[k+1][j]+qz[j]-qz[i]+w[i],minn); //转移
}
dp[i][j]=minn;
}
}
cout<<dp[1][n]<<endl;
}
return 0;
}
/*
4
4 5 9 4

43
54
*/