区间dp 用f[i][j]来表示区间[i,j]的最小体力值，初始值为1e9； dp的方式依个人而定，这里用的是列举区间长度，在逐间推移； 由于时间复杂度的限制，在dp中累加是不明智的，要用前缀和来计算区间的和

using namespace std;
int f[305][305];
int a[305];
int sum[305];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];//边输入边计算前缀和
	}
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n;j++)
			if(i!=j)
				f[i][j]=1e9;
	for(int l=1;l<=n;l++)
		for(int i=1;i<=n-l+1;i++)
		{
			int j=i+l-1;//计算右端点
			for(int k=i;k<j;k++)
			{
				f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]-sum[i-1]+sum[j]);
			}
		}
	cout<<f[1][n];
	return 0;
}