我是傻逼
```cpp
#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]!=dp[0][0]){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];
}
by clx201022 @ 2023-02-24 20:41:56
留贴于此,警示后人
by clx201022 @ 2023-02-24 20:42:54