737-石子合并（一）

内存限制:64MB 时间限制:1000ms 特判: No

通过数:30 提交数:37 难度:3

题目描述:

有N堆石子排成一排，每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆，每次合并花费的代价为这两堆石子的和，经过N-1次合并后成为一堆。求出总的代价最小值。

输入描述:

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

输出描述:

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

样例输入:

31 2 3713 7 8 16 21 4 18

样例输出:

AC代码

参考大佬博客：

/** @Author: WZY* @School: HPU* @Date:   2018-10-11 16:28:28* @Last Modified by:   WZY* @Last Modified time: 2018-10-11 16:54:57*/#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #define ll long long#define ull unsigned long long#define ms(a,b) memset(a,b,sizeof(a))#define pi acos(-1.0)#define INF 0x7f7f7f7f#define lson o<<1#define rson o<<1|1#define debug(...) cerr<<"["<<#__VA_ARGS__":"<<(__VA_ARGS__)<<"]"<<"\n"const double E=exp(1);const int maxn=1e3+10;const int mod=1e9+7;using namespace std;int dp[maxn][maxn];int sum[maxn][maxn];int a[maxn];int main(int argc, char const *argv[]){ ios::sync_with_stdio(false); #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); double _begin_time = clock(); #endif int n; while(cin>>n) { ms(sum,0); ms(a,0); ms(dp,INF); for(int i=1;i<=n;i++) { cin>>a[i]; sum[i][i]=a[i]; dp[i][i]=0; } // 枚举长度 for(int len=1;len

转载于:https://www.cnblogs.com/Friends-A/p/10324344.html

你可能感兴趣的文章