描述

有n堆石子排成一行，每次选择相邻的两堆石子，将其合并为一堆，该次合并的消费为两堆石子个数之和。已知每堆石子的石子个数，求当所有石子合并为一堆时，最小的消费。

输入

有多组测试数据，输入到文件结束。
每组测试数据第一行有一个整数n，表示有n堆石子。
接下来的一行有n（0< n <200）个数，分别表示这n堆石子的数目，用空格隔开

输出

输出总代价的最小值，占单独的一行

样例

Input
3
1 2 3
7
13 7 8 16 21 4 18

Output
9
239

思路

用dp[i][j]表示区间[i,j]的最小花费。(N^2)枚举区间[i,j]，用断点k遍历i~j，则dp[i][j]=min(dp[i][k]+dp[k][j]+sum[j]-sum[i-1])，其中sum[i]为i的前缀和。时间复杂度为O(N^3)

Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

#include
         
           #define INIT(a,b) memset(a,b,sizeof(a)) #define LL long long int using namespace std; const int MAX=0x7fffffff; const int MIN=-0x7fffffff; const int INF=0x3f3f3f3f; const int Mod=1e9+7; const int MaxN=1e7+7; int main(){
            //freopen("1.in","r",stdin);     //freopen("1.out","w",stdout);     int n,dp[201][201];     int sum[201],x;     cin>>n;     INIT(sum,0);     for(int i=0;i<=n;i++)         for(int j=0;j<=n;j++)             dp[i][j]=INF;     for(int i=1;i<=n;i++){
                cin>>x;         sum[i]=sum[i-1]+x;         dp[i][i]=0;     }     for(int len=2;len<=n;len++){
                for(int i=1;i+len-1<=n;i++){
                    int j=i+len-1;             for(int k=i;k

转载地址：https://blog.csdn.net/cpongo3/article/details/89334316 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

描述

输入

输出

样例

思路

Code

发表评论

最新留言

关于作者

推荐文章