#include <cstdio>
using namespace std;
const int maxn = 13005;
int m[maxn][maxn];
int a[maxn][maxn],cost[maxn];
int N,A,i,j;

int te;
int main()
{
scanf("%d",&N);
cost[0]=0;

for(i=1;i<=N;i++)
{
scanf("%d",&cost[i]);
cost[i]+=cost[i-1];
}
for(i=1;i<=N;i++)
{
m[i][i]=0;
a[i][i]=i;
}
for(i=N;i>=1;i--)
{
for(j=i+1;j<=N;j++)
{
int ans=1<<29;
for(int k=a[i][j-1];k<=a[i+1][j];k++)
{
if(ans>m[i][k]+m[k+1][j]+cost[j]-cost[i-1])
{
ans=m[i][k]+m[k+1][j]+cost[j]-cost[i-1];
te=k;
}
}
m[i][j]=ans;
a[i][j]=te;
}

}
printf("%d",m[1][N]);
return 0;
}
题有问题没法ac