// 我们的f[i,j]在每次开始的时候都要初始化为一个大的数，因为初始都是0
// f[i,j]=min(f[i,k],f[k+1][j])+s[j]-s[i-1]  前缀和
// k: i~j-1

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 310;
int n;
int a[N];
int s[N];   //保存前缀和
int f[N][N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i ++ ) s[i]=s[i-1]+a[i];
    for(int len=2;len<=n;len++) //区间DP
    {
        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<i+len-1;k++)  //划分点k是从l到r的过程
                                        //分割点其实是往左包含的，当k==i时就是左边一个的分割
                                        //当k==r-1时就只有右边一个数留下，时最后一个分割点，合理
            {
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
            }
        }
    }
    cout << f[1][n];
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 310;
int n;
int arr[N];
int s[N];
int f[N][N];

int main()
{
    cin>>n;
    for (int i = 1; i <= n; i ++ ) cin>>arr[i];
    for (int i = 1; i <= n; i ++ ) s[i]=s[i-1]+arr[i];

    for(int len=2;len<=n;len++) //len=2
    {
        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++)
            {
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
            }
        }
    }
    cout<<f[1][n];
}