1     #include <iostream>   2     #include <string.h>   3     #include <stdio.h>   4        5     using namespace std;   6     const int INF = 1 << 30;   7     const int N = 205;   8        9     int dp[N][N];  10     int sum[N];  11     int a[N];  12       13     int getMinval(int a[],int n)  14     {  15         for(int i=0;i<n;i++)  16             dp[i][i] = 0;  17         for(int v=1;v<n;v++)  18         {  19             for(int i=0;i<n-v;i++)  20             {  21                 int j = i + v;  22                 dp[i][j] = INF;  23                 int tmp = sum[j] - (i > 0 ? sum[i-1]:0);  24                 for(int k=i;k<j;k++)  25                     dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j] + tmp);  26             }  27         }  28         return dp[0][n-1];  29     }  30       31     int main()  32     {  33         int n;  34         while(scanf("%d",&n)!=EOF)  35         {  36             for(int i=0;i<n;i++)  37                 scanf("%d",&a[i]);  38             sum[0] = a[0];  39             for(int i=1;i<n;i++)  40                 sum[i] = sum[i-1] + a[i];  41             printf("%d\n",getMinval(a,n));  42         }  43         return 0;  44     }