学步园

http://acm.nyist.net/JudgeOnline/problem.php?pid=737

经典区间DP

入门题

 
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define INF 99999999
int const MAXN = 300;
int sum[MAXN],dp[MAXN][MAXN];
inline int Max(int a,int b){
    return a>b?a:b;
}
inline int Min(int a,int b){
    return a<b?a:b;
}
int main(){
    int n;
    while(~scanf("%d",&n)){
        memset(sum,0,sizeof(sum));
        for(int i = 1;i <= n;i++){
            int x;
            scanf("%d",&x);
            sum[i] = sum[i - 1] + x;
        }
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= n;j++){
                dp[i][j] =(i == j ?0:INF);
            }
        }
        for(int l = 2;l <= n;l++){//区间长度
            for(int i = 1;i <= n - l + 1;i++){//区间起点
                int j = i + l - 1;
                int x = sum[j] - sum[i - 1];
                for(int k = 1;k < j;k++){
                    dp[i][j] = Min(dp[i][j],dp[i][k] + dp[k + 1][j] + x);
                }
            }
        }
        printf("%d\n",dp[1][n]);
    }
    return 0;
}