#include<bits/stdc++.h>
using namespace std;
int n,dp[1005][1005],sum[1005];
const int d=0x3f;
int dfs(int l,int r);
int main()
{
    cin>>n;
    memset(dp,d,sizeof(dp));
    /*
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            cout<<dp[i][j]<<'\n';
        }
    }*/
    for(int i=1;i<=n;i++)
    {
        cin>>sum[i];
        sum[i]+=sum[i-1];//前缀和
    }
    cout<<dfs(1,n);
    return 0;
}
int dfs(int l,int r)
{
    if(l==r)return 0;//石子免费和自身合并
    if(dp[l][r]!=d){return dp[l][r];}//dp有值的话
    for(int k=l;k<r;k++)
    {
        dp[l][r]=min(dp[l][r],dfs(l,k)+dfs(k+1,r)+sum[r]-sum[l-1]);
    }
    return dp[l][r];
}

代码求调