A. 石子合并<1>

内存限制：128 MiB 时间限制：1000 ms 标准输入输出

题目类型：传统评测 方式：文本比较

 

题目描述

有N堆石子排成一排(n<=100),现要将石子有次序地合并成一堆，规定每次只能选相邻的两堆合并成一堆，并将新的一堆的石子数，记为改次合并的得分，编一程序，由文件读入堆数n及每堆石子数(<=200)；

（1）选择一种合并石子的方案，使得做n-1次合并，得分的总和最少

（2）选择一种合并石子的方案，使得做n-1次合并，得分的总和最多

输入格式

第一行为石子堆数n 第二行为每堆石子数，每两个数之间用一空格分隔。

输出格式

从第1行为得分最小第二行是得分最大。

样例输入

4

4 5 9 4

样例输出

44

54

分析：

附上代码（有注释）：

1 #include 
          
            2 #include 
           
             3 #include 
            
              4 using namespace std; 5 const int maxp=210; 6 int n,t[maxp],//t[i]:第i堆石子的个数  7 f_min[maxp][maxp],//f_min[i][j]:从i到j的最小得分  8 f_max[maxp][maxp],//f_max[i][j]:从i到j的最大得分  9 sum[maxp];//sum[i]:从1到i的石子总和 10 int main(){11     memset(f_min,0x3f,sizeof(f_min));//以上是进行初始值 min要给一个大的值，否则结果0 12     scanf("%d",&n);13     for(int i=1;i<=n;++i)14         scanf("%d",&t[i]);//以上是输入 15     for(int i=1;i<=n;++i)16         sum[i]=sum[i-1]+t[i];17     for(int i=1;i<=n;i++)18         f_min[i][i]=0; //从i到i的最小合并恰好是0 19     for(int len=1;len