#include <iostream>
#include <stdio.h>
using namespace std;

//石頭合并問題 PKU 1086 動(dòng)態(tài)規(guī)劃
/*
輸入：
4
4  1  2  3

輸出：
*/
#define MAX 1000000000
int a[202];//每個(gè)石頭的重量
long f[202][202];//f[i][j]，第i個(gè)石頭分到第j個(gè)石頭合并的最小代價(jià)
long sum[202][202];//sum[i][j],第i個(gè)石頭到第j個(gè)石頭的重量之和

void print(int num)
{
	int i,j;
	for(i=1;i<=num;i++)
	{
		for(j=1;j<=num;j++)
			printf("%3d",f[i][j]);
		cout<<endl;
	}
	cout<<endl;
	system("pause");
}

void cal(int num)
{
	int i,j,k,min,d;
	for(i=1;i<=num;i++)
		f[i][i]=0;//不合并時(shí)的代價(jià)
	for(i=1;i<num;i++)
	{
		sum[i][i]=a[i];
		for(j=i+1;j<=num;j++)
		{
			sum[i][j]=sum[i][j-1]+a[j];
		}
	}
	sum[num][num]=a[num];
	for(d=1;d<=num-1;d++)
	{
		for(i=1;i<=num-d;i++)
		{
			j=i+d;
			min=MAX;
			//i..k為一堆石頭，k+1,k+2...j為另一堆石頭
			//f[i][j]為f[i][k]+f[k+1][j]+sum[i][j]的最小值(i<=j<k)
			for(k=i;k<j;k++)
				if(min>f[i][k]+f[k+1][j]+sum[i][j]) min=f[i][k]+f[k+1][j]+sum[i][j];
			f[i][j]=min;
			print(num);
		}
	}
}

int main()
{
	int num,i;
	scanf("%d",&num);
	for(i=1;i<=num;i++)
		cin>>a[i];
	cal(num);
	cout<<f[1][num]<<endl;
	return 0;
}