Description

做如下两个模型的石子合并，如下模型石子都不能移动出列，且合并都仅发生在相邻两堆石子中：

（1）第一个模型：一行排列且相邻合并
有n堆石子A1,A2,...,An形成一行，每堆石头个数记为ai(1<=i<=n)，相邻两堆可合并，合并的分值为新堆的
石子数。求合并为一堆的最低得分和最高得分。

（2）第二个模型：一圈排列且相邻合并
有n堆石子A1,A2,...,An形成首位相连的一个环形，An和A1相邻，每堆石头个数记为ai(1<=i<=n)，相邻两堆
可合并，合并的分值为新堆的石子数。求合并为一堆的最低得分和最高得分。

例如4堆石子，每堆石子个数：9 4 4 5
若排成一行，最小分值：(4+4)+(8+5)+(9+13)=43，最大分值：(9+4)+(13+4)+(17+5)=52。
若排成圈状，最小分值：(4+4)+(8+5)+(9+13)=43，最大分值：(9+5)+(14+4)+(18+4)=54。

此题以第一模型的最低得分为例，很多同学想着采用总是从最小的相邻两堆下手的思想，认为最后获得的也就是最
低得分。但这个贪心策略是不对的。如下反例：

石子：9 4 6 1 5

贪心策略：
9 4 6 6      计分6
9 10 6       计分10
9 16         计分16
25           计分25
得分共计：6+10+16+25=57

但9 4 6 1 5 若如下方式合并：
13 6 1 5     计分13
13 6 6       计分6
13 12        计分12
25           计分25
13+6+12+25=56

或
9 4 6 6      计分6
9 4 12       计分12
13 12        计分13
25           计分25
6+12+13+25=56

后两种方式合并出的56都比贪心策略的57来的更低，因为总选择最小的相邻两堆去合并，并不能保证后续每步
都可以最小，也许这轮最小导致后续几轮分值较大。

输入格式

两行。第一行n，第二行a1 a2 … an，每个ai(1<=i<=n)表示第i堆石子的个数，n<=100

输出格式

两行。第一行是第一个模型的最低得分和最高得分，中间空格相连，第二行是第二个模型的最低得分和
最高得分，中间空格相连。

输入样例

4
9 4 4 5

输出样例

43 52
43 54

提示

（1）第一个石子合并模型

和书上3.1节的矩阵连乘问题类似。假设m[i,j]为合并石子ai…aj，1<=i<=j<=n。所得到的最小
得分，若没有“合并”这个动作，则为0。
原问题所求的合并最小值即为m[1,n]。

递推公式如下，其中min表示求最小，sum表示求和。
    m[i,j] = 0,   if i=j
    m[i,j] = min{ m[i,k]+m[k+1,j] | for all k, i<=k<j } + sum{ a(t) | for all t, i<=t<=j },
                  if i<j

至于求最大值完全同理，自行推导递归公式。


（2）第二个石子合并的环型模型

方法一、环型模型完全可以转化为行型模型来求解。
环形模型可视为等价的行形模型： A1 ... An A1 ... An-1，共2n-1堆，并在此行形模型中合并石头不超过
链长n。
环型模型问题所求，不是等价模型所填充的右上方元素m[1,2n-1]，而是m[1,n], m[2,n+1], …, m[n,2n-1]
这n个斜行元素中的最小值，
即： min{ m[i, n+i-1] | for all i, 1<=i<=n }


方法二、定义链，但环型定义链如果和前面行型一样，用链的起始和结束下标的话，不好定义，我们得换一
种定义方式，加入链长这个参数而去掉结束下标这个参数。

定义环型的链p(i,r)，表示石头堆链Ai, A[(i+1)%n], ..., A[(i+r-1)%n]。  那链p(i,r)能够合并的最小分
值记为m(i,r)。这里，1<=i<=n, 1<=r<=n。

Ai  ...  A[(i+s-1)%n]    A[(i+s)%n]  ...  A[(i+r-1)%n]
---------------------    -----------------------------
      s个（链长s）                r-s个（链长r-s）

最后一次合并在A[(i+s-1)%n]和A[(i+s)%n]之间，分为两个子链，左一个子链是p(i,s)，右一个子链是p((i+s)%n, r-s)。
链p(i,r)的最优值（最小值）由两个子链的最优值（最小值）得到。

   m(i,r) = 0     r=1;
   m(i,r) = min{ m(i,s)+m((i+s)%n, r-s) | for all s, 1<=s<r} + sum{a(t) | for all t, i<=t<=(i+r-1)%n }
               1<r<=n

由链长增加的方向来填充m(i,r)数组，原问题所求为： min{m(i,n) | 1<=i<=n}

例如： n=5，  A1 A2 A3 A4 A5 构成环型。
计算：
r=1, m[i,1] （1<=i<=n）， 即：m[1,1], m[2,1], m[3,1], m[4,1], m[5,1]。 
对应的矩阵链为：A1, A2, A3, A4, A5；
r=2, m[i,2] （1<=i<=n）， 即：m[1,2], m[2,2], m[3,2], m[4,2], m[5,2]。 
对应的矩阵链为：A1A2, A2A3, A3A4, A4A5, A5A1；
r=3, m[i,3] （1<=i<=n）， 即：m[1,3], m[2,3], m[3,3], m[4,3], m[5,3]。 
对应的矩阵链为：A1A2A3, A2A3A4, A3A4A5, A4A5A1, A5A1A2；
......
r=n, m[i,n] （1<=i<=n）， 即：m[1,n], m[2,n], m[3,n], m[4,n], m[5,n]。 
对应的矩阵链为：A1A2...An, A2A3...A1, A3A4...A2, A4A5...A3, A5A1...A4；

对m二维数组一列一列填充，原问题所求环型的最小得分为最后填充的一列m元素：
m[1,n], m[2,n], m[3,n], m[4,n], m[5,n]的最小值，即 min{m(i,n) | 1<=i<=n}。

我的代码实现

  1 #include<stdio.h>
  2 
  3 #define N 1000
  4 int min[N][N],max[N][N];
  5 
  6 int sum(int p[],int i,int j){
  7     int t;
  8     int total=0;
  9     for(t=i;t<=j;t++){
 10         total+=p[t];
 11     }
 12     return total;
 13 }
 14 
 15 
 16 void MatrixChainMin1(int p[],int n){
 17     for(int i=1;i<=n;i++){
 18         min[i][i]=0;
 19     }
 20     for(int r=2;r<=n;r++){
 21         for(int i=1;i<=n-1;i++){
 22             int j=i+r-1;
 23             min[i][j]=min[i+1][j]+sum(p,i,j);    
 24                 for(int k=i+1;k<j;k++){
 25                     int t=min[i][k]+min[k+1][j]+sum(p,i,j);
 26                     if(t<min[i][j]){min[i][j]=t;}
 27                     }
 28             }
 29     }
 30 } 
 31 
 32 
 33 
 34 
 35 void MatrixChainMax1(int p[],int n){
 36     for(int i=1;i<=n;i++){
 37         max[i][i]=0;
 38     }
 39     for(int r=2;r<=n;r++){
 40         for(int i=1;i<=n-1;i++){
 41             int j=i+r-1;
 42             max[i][j]=max[i+1][j]+sum(p,i,j);
 43                 for(int k=i+1;k<j;k++){
 44                     int t=max[i][k]+max[k+1][j]+sum(p,i,j);
 45                     if(t>max[i][j]){max[i][j]=t;}
 46                     }
 47             }
 48     }
 49 } 
 50 
 51 
 52 void MatrixChainMin2(int p[],int n){
 53     for(int i=1;i<=n;i++){
 54         min[i][i]=0;
 55     }
 56     for(int r=2;r<=(n+1)/2;r++){
 57         for(int i=1;i<=n-1;i++){
 58             int j=i+r-1;
 59             min[i][j]=min[i+1][j]+sum(p,i,j);    
 60                 for(int k=i+1;k<j;k++){
 61                     int t=min[i][k]+min[k+1][j]+sum(p,i,j);
 62                     if(t<min[i][j]){min[i][j]=t;}
 63                     }
 64             }
 65     }
 66 } 
 67 
 68 void MatrixChainMax2(int p[],int n){
 69     for(int i=1;i<=n;i++){
 70         max[i][i]=0;
 71     }
 72     for(int r=2;r<=(n+1)/2;r++){
 73         for(int i=1;i<=n-1;i++){
 74             int j=i+r-1;
 75             max[i][j]=max[i+1][j]+sum(p,i,j);    
 76                 for(int k=i+1;k<j;k++){
 77                     int t=max[i][k]+max[k+1][j]+sum(p,i,j);
 78                     if(t>max[i][j]){max[i][j]=t;}
 79                     }
 80             }
 81     }
 82 } 
 83 
 84 
 85 
 86 int CircleMin(int n){
 87     int min1=min[1][n];
 88     for(int i=1;i<=n;i++){
 89         if(min1>min[i][n+i-1])min1=min[i][n+i-1];
 90 //        printf("%d ",min[i][n+i-1]);
 91     }
 92 //    printf("
");
 93     return min1;
 94 }
 95 
 96 int CircleMax(int n){
 97     int max1=max[1][n];
 98     for(int i=1;i<=n;i++){
 99         if(max1<max[i][n+i-1])max1=max[i][n+i-1];
100 //        printf("%d ",max[i][n+i-1]);
101     }
102 //    printf("
");
103     return max1;
104 }
105 
106 
107 int main(){
108     int n;
109     int p[N];
110     scanf("%d",&n);
111     for(int i=1;i<=n;i++){
112         scanf("%d",&p[i]);
113     }
114     MatrixChainMin1(p,n);
115     MatrixChainMax1(p,n);
116     for(int i=1;i<=n-1;i++){
117         p[n+i]=p[i];
118     }
119     MatrixChainMin2(p,2*n-1);
120     MatrixChainMax2(p,2*n-1);
121     printf("%d ",min[1][n]);
122     printf("%d
",max[1][n]);
123     printf("%d ",CircleMin(n));
124     printf("%d",CircleMax(n));    
125     return 0;
126 }