#include<bits/stdc++.h> #define int long long using namespace std; int n,a[10001],s[10001],**dp; signed main() { cin>>n; dp=new int*[n+1]; for(int i=1;i<=n;i++) { dp[i]=new int[n+1]; for(int j=1;j<=n;j++) dp[i][j]=LONG_LONG_MAX; } for(int i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]+a[i],dp[i][i]=0; for(int len=2;len<=n;len++) for(int i=1;i+len-1<=n;i++) { int j=i+len-1; for(int k=i;k<j;k++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+s[j]-s[i-1]); } cout<<dp[1][n]; for(int i=1;i<=n;i++) delete[] dp[i]; delete[] dp; }