1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #define CLR(a,b) memset((a),(b),sizeof((a))) 5 using namespace std; 6  7 const int inf = 0x3f3f3f3f; 8 const int N = 101; 9 int n;10 int a[N];11 int dp[N][N];//i到j合并的最小值12 int sum[N];13 int main(){14     int t, i, j, k, len;15     sum[0] = 0;16     scanf("%d", &n);17     for(i = 1; i <= n; ++i){18         scanf("%d", &a[i]);19         sum[i] = sum[i - 1] + a[i];20     }21     for(i = 1 ;i <= n; ++i)22         dp[i][i] = 0;23     for(len = 2; len <= n; ++len){//合并的长度24         for(i = 1; i <= n - len + 1; ++i){//起点25             j = i + len - 1;//终点26             dp[i][j] = inf;27             for(k = i; k < j; ++k){28                 dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1]);29             }30         }31     }32     printf("%d\n", dp[1][n]);33     return 0;34 }