46-伪代码详解

4.8.4　伪代码详解

（1）路边玩法

首先初始化Min[i][i]=0，Max[i][i]=0，sum[0]=0，计算sum[i]，其中i= 1，2，3，…，n。

循环阶段：

按照递归式计算2堆石子合并{a_i，a_i+1}的最小花费和最大花费，i=1，2，3，…，n−1。

按照递归式计算3堆石子合并{a_i，a_i+1，a_i+2}的最小花费和最大花费，i=1，2，3，…，n−2。

以此类推，直到求出所有堆{a₁，…，a_n}的最小花费和最大花费。

void straight(int a[],int n)
{
     for(int i=1;i<=n;i++)               // 初始化
          Min[i][i]=0, Max[i][i]=0;
     sum[0]=0;
     for(int i=1;i<=n;i++)
         sum[i]=sum[i-1]+a[i];
     for(int v=2; v<=n; v++)             // 枚举合并的堆数规模
     {
          for(int i=1; i<=n-v+1; i++)    //枚举起始点i
          {
               int j = i + v-1;          //枚举终点j
               Min[i][j] = INF;          //初始化为最大值
               Max[i][j] = -1;           //初始化为-1
               int tmp = sum[j]-sum[i-1];//记录i...j之间的石子数之和
               for(int k=i; k<j; k++) {  //枚举中间分隔点
                    Min[i][j] = min(Min[i][j], Min[i][k] + Min[k+1][j] + tmp);
                    Max[i][j] = max(Max[i][j], Max[i][k] + Max[k+1][j] + tmp);
               }
          }
     }
}

（2）操场玩法

圆型石子合并经常转化为直线型来求，也就是说，把圆形结构看成是长度为原规模两倍的直线结构来处理。如果操场玩法原问题规模为n，所以相当于有一排石子a₁，a₂，…，a_n，a₁，a₂，…，a_n−1，该问题规模为2n−1，然后就可以用线性的石子合并问题的方法求解，求最小花费和最大花费的方法是一样的。最后，从最优解中找出规模是n的最优解即可。

即要从规模为n的最优解Min[1][n]，Min[2][n+1]，Min[3][n+2]，…，Min[n][2n−1]中找最小值作为圆型石子合并的最小花费。

从Max[1][n]，Max[2][n+1]，Max[3][n+2]，…，Max[n][2n−1] 中找出最大值作为圆型石子合并的最大花费。

void Circular(int a[],int n)
{
     for(int i=1;i<=n-1;i++)
          a[n+i]=a[i];
     n=2*n-1;
     straight(a, n);
     n=(n+1)/2;
     min_Circular=Min[1][n];
     max_Circular=Max[1][n];
     for(int i=2;i<=n;i++)
     {
          if(Min[i][n+i-1]<min_Circular)
              min_Circular=Min[i][n+i-1];
          if(Max[i][n+i-1]>max_Circular)
              max_Circular=Max[i][n+i-1];
     }
}