图片说明
图片说明
图片说明
原文链接链接
有效的将的区间dp优化成

题目 1898: [蓝桥杯][算法提高VIP]合并石子

在一条直线上有n堆石子，每堆有一定的数量，每次可以将两堆相邻的石子合并，合并后放在两堆的中间位置，合并的费用为两堆石子的总数。求把所有石子合并成一堆的最小花费。

code

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
const int INF = 1 << 30;
int sum[MAXN],n;

int Minval(){
    int dp[MAXN][MAXN],s[MAXN][MAXN];
    for(int i=1;i<=n;++i){
        dp[i][i]=0;
        s[i][i]=i;
    }
    for(int len=1;len<n;++len){
        for(int i=1;i<=n-len;++i){
            int j=i+len;
            dp[i][j]=INF;
            for(int k=s[i][j-1];k<=s[i+1][j];++k){
                if(dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]<dp[i][j]){
                    dp[i][j]=dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1];
                    s[i][j]=k;
                }
            }
        }
    }
    return dp[1][n];
}                      

int main(void){
    while(cin>>n){
        sum[0]=0;
        for(int i = 1 ; i <= n ; ++i){
            int x;
            cin>>x;
            sum[i]=sum[i-1]+x;
        }
        cout << Minval() <<endl;
    }
    return 0;
}