P1055 （C++代码）

解题思路:





注意事项:





参考代码:

#include <bits/stdc++.h>  
using namespace std;  
#define maxn 1000+5  
#define INF 1<<29  
int dp[maxn][maxn];  
int a[maxn],sum[maxn];  
int main()  
{  
    int N;  
    scanf("%d",&N);  
    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++)//注意len=1情况  
    {  
        for(int i=1;i<=N-len+1;i++)//i表示起点  
        {  
            int end=i+len-1;  
            int minsum=INF;  
            for(int k=i;k<end;k++)//不取等于  
            {  
               minsum=min(minsum,dp[i][k]+dp[k+1][end]+sum[end]-sum[i-1]);  
            }  
            dp[i][end]=minsum;  
        }  
    }  
    printf("%d\n",dp[1][N]);  
    return 0;  
}