提交时间:2024-05-25 15:23:19
运行 ID: 148968
#include<bits/stdc++.h> using namespace std; const int N=110; int dp[N][N]; int len; int a[N]; int n,sum[N]; int main(){ scanf("%d",&n); memset(dp,0x3f,sizeof(dp)); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); sum[i]=sum[i-1]+a[i]; dp[i][i]=0; } for(int len=2;len<=n;len++){ for(int i=1;i<=n-len+1;i++){ int j=i+len-1; for(int k=i;k<j;k++){ dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]); } } } printf("%d\n",dp[1][n]); return 0; }