将 n 堆石子绕圆形操场排放，现要将石子有序地合并成一堆。

规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。

请编写一个程序，读入堆数 n 及每堆的石子数，并进行如下计算：

• 选择一种合并石子的方案，使得做 n−1 次合并得分总和最大。
• 选择一种合并石子的方案，使得做 n−1 次合并得分总和最小。

输入格式

第一行包含整数 n，表示共有 n 堆石子。

第二行包含 n 个整数，分别表示每堆石子的数量。

输出格式

输出共两行：

第一行为合并得分总和最小值，

第二行为合并得分总和最大值。

数据范围

1≤n≤200

输入样例：

4
4 5 9 4

输出样例：

43
54

代码：

/*
在区间DP中，我们也常常省去 len 这一维的空间

因为 r−l+1=len，也就保证了在已知 l 和 r 的情况下，不会出现状态定义重复的情况

根据线性代数中方程的解的基本概念，我们就可以删掉 len 这一维不存在的约束

但为了方便读者理解，以及介绍区间DP的阶段是如何划分的，我还是写了出来
*/
#include <bits/stdc++.h>
using namespace std;

const int N = 410;
int f[N][N], g[N][N];
int w[N], s[N];
int n;

int main()
{
    cin >> n;
    // 化环为链 n个点n-1条边 一定有两个点之间断开
    for (int i = 1; i <= n; i++)
    {
        cin >> w[i];
        w[i + n] = w[i];
    }

    memset(f, 0x3f, sizeof f);
    memset(g, -0x3f, sizeof g);

    for (int i = 1; i <= 2 * n; i++)
        f[i][i] = g[i][i] = 0;

    for (int i = 1; i <= 2 * n; i++)
        s[i] = s[i - 1] + w[i];

    for (int len = 2; len <= n; len++)
    {
        for (int i = 1; i + len - 1 <= 2 * n; i++)
        {
            int j = i + len - 1;
            for (int k = i; k < j; k++)
            {
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
                g[i][j] = max(g[i][j], g[i][k] + g[k + 1][j] + s[j] - s[i - 1]);
            }
        }
    }

    int minn = 0x3f3f3f3f, maxx = 0;
    for (int i = 1; i <= n; i++)
    {
        minn = min(minn, f[i][i + n - 1]);
        maxx = max(maxx, g[i][i + n - 1]);
    }

    cout << minn << endl
         << maxx << endl;
    return 0;
}

算法–环形石子合并问题设计过程

一.问题描述：在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。
要求：对于任意给定的n堆石子,计算合并成一堆的最小得分和最大得分。
二、问题及解决方案
1）审题不清：题目要求的是将每两堆石子合并之后的数量与下一次合并之后的数量相加求得分，我们一开始理解成：相邻两堆石子合并后，用合并后的石子数量再与相邻石子合并相加求得分，如果这样想的话，最后的得分就是一个定值，即所有石子数之和，也就不存在最大得分和最小得分了。
2）方法的使用：
开始以为通过贪心算法可能很快解决问题，可是是行不通的。
首先我们可以把这么堆石子看成一列，我们假如5堆的石子，其中石子数分别为7，6，5，7，100
按照贪心法，合并的过程如下： 每次合并得分
第一次合并 7 6 5 7 100 =11
第二次合并 7 11 7 100=18
第三次合并 18 7 100 =25
第四次合并 25 100 =125
总得分＝11＋18＋25+125＝179

另一种合并方案 每次合并得分
第一次合并 7 6 5 7 100 ->13
第二次合并 13 5 7 100->12
第三次合并 13 12 100 ->25
第四次合并 25 100 ->125
总得分＝13＋12＋25+125＝175
由此可以看出，利用贪心法来做是错误的，贪心算法在子过程中得出的解只是局部最优,而不能保证使得全局的值最优。
三、算法设计
如果N－1次合并的全局最优解包含了每一次合并的子问题的最优解，那么经这样的N－1次合并后的得分总和必然是最优的。
因此我们需要通过动态规划算法来求出最优解。
在此我们假设有n堆石子，一字排开，合并相邻两堆的石子，每合并两堆石子得到一个分数，最终合并后总分数最少的。
我们设m(i,j)定义为第i堆石子到第j堆石子合并后的最少总分数。a(i)为第i堆石子的石子数量。
当合并的石子堆为1堆时，很明显m(i,i)的分数为0;
当合并的石子堆为2堆时，m(i,i+1)的分数为a(i)+a(i+1);
当合并的石子堆为3堆时，m(i,i+2)的分数为MIN((m(i,i)+m(i+1,i+2)+sum(i,i+2)),(m(i,i+1)+m(i+2,i+2)+sum(i,i+2));
当合并的石子堆为4堆时…

（1）求最小得分相应的代码如下：
int MatrixChain_min(int p[N],int n)//p[N]石子数，n石子堆数
{
int m[N][N]; //定义二维数组m[i][j]来记录i到j的合并过成中最少石子数目（石子积分）

int min=0;                                                     
   for(int g = 1;g<=n;g++)
		m[g][g]=0;  //当一个单独合并时，m[i][i]设为0，表示没有积分。
                                                        
	for(int i=1;i<=n-1;i++)//当相邻的两堆石子合并时，此时的m很容易可以看出是两者之和。
	{
      int j=i+1;
      m[i][j]=p[i]+p[j];
    }
                                                     
	for(int r=3; r<=n;r++)//当相邻的3堆以及到最后的n堆时，执行以下循环（r表示考虑到了多堆石子合并的所有情况） 
       for(int i=1;i<=n-r+1;i++)//i表示开始的那一堆，j表示最后的那一堆 
       {
           int j = i+r-1; //j总是距离i r-1的距离                           
           int fin=0;                                  
           for(int b=i;b<=j;b++)//当i到j堆石子合并时最后里面的石子数求和得fin（fin是所有的石子数） 
               fin+=p[b];

           // 此时m[i][j]为i~j堆石子间以m[i][i]+m[i+1][j]+fin结果，这是其中一种可能，不一定是最优
           //要与下面的情况相比较

            m[i][j] = m[i+1][j]+fin;//最初的积分情况 

           //除上面一种组合情况外的其他组合情况
           for(int k=i+1;k<j;k++)//进行比较 
           {
               int t=m[i][k]+m[k+1][j]+fin;//后来情况的积分 
               if(t<m[i][j])
                   m[i][j] = t;

           }
       }
        //最终得到最优解
       min=m[1][n]; //最小的情况赋值给min 
       return min;
      
}

（2）最大得分的求法与最小得分的求法是相同的道理；

（3）我们回到解法的开始：假设的是石子一次排开求最大得分和最小得分，而题目要求的是：石子以圆形排开，因此我们在主函数中应用了相应方法来达到要求，代码如下：
int main()
{
int stone[N];//每堆石子数
int min=0;//最小的分初始化
int max=0;//最大的分初始化
int n;//石子堆数
printf(“请输入石子堆数：”);
scanf("%d",&n);
for(int i=1;i<=n;i++){
printf(“请输入第%d堆石子数：”,i);
scanf("%d",&stone[i]);
}
min= MatrixChain_min(stone,n);//传到子函数
max= MatrixChain_max(stone,n);//传到子函数

   //因为题目要求圆的原因，要把所有情况都要考虑到，总共有n种情况。
   for(int j=1;j<=n-1;j++)
   {
        int min_cache=0;//积分最小情况 
        int max_cache=0;//积分最大情况
        int cache= stone[1];
        for(int k=2;k<=n;k++)
        {
            stone[k-1]=stone[k];
        }
        stone[n]=cache;
        min_cache= MatrixChain_min(stone,n);
        max_cache= MatrixChain_max(stone,n);
        if(min_cache<min)
           min=min_cache;
        if(max_cache>max)
            max=max_cache;
  }

printf("最小得分：%d\n",min);
printf("最大得分：%d\n",max);
 return 1;

}
总的来说就是：在循环中，通过cache这个中间变量，让每一堆石子都有成为第一堆的机会，满足圆形的要求，然后用排序之后的石子调用上面的方法，得到新的得分数，分别与之前的最大得分和最小得分进行比较，得到最终的最大得分和最小得分。

原题链接- AcWing 

分析：与石子合并只加了一个环形的条件

对于环形问题，如果只是枚举中断点的话，在石子合并的基础上多开一维，时间复杂度是O(n^4)

可以采用一个普遍的方法，就是把环转换成一个链

 通过把从1展开的链接在n的后面，这样子枚举的时候枚举以 位置2 断开的链，只需要枚举 以2开始，长度为len的链，就可以枚举n与1相邻的情况了

状态转移方程基本和石子合并一样，不同点在于环的存在，导致循环枚举不同

for(int len=1;len<=n;len++)
        for(int l=1;l+len-1<=2*n;l++)
        {//由于模拟中间断点,把前面断开的接到数组后面去，所以最大可能枚举到2n

           ...
        }

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=410;
int a[N];
int s[N];
int dp[N][N];
int g[N][N];

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],a[n+i]=a[i];
    
    for(int i=1;i<=2*n;i++) s[i]=s[i-1]+a[i];
    
    memset(dp,0x3f,sizeof dp),memset(g,-0x3f,sizeof g);
    
    for(int len=1;len<=n;len++)
        for(int l=1;l+len-1<=2*n;l++)
        {
            int r=l+len-1;
            if(len==1) dp[l][r]=g[l][r]=0;
            else
                for(int k=l;k<r;k++)
                {
                    dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+s[r]-s[l-1]);
                    g[l][r]=max(g[l][r],g[l][k]+g[k+1][r]+s[r]-s[l-1]);
                }
        }
    int maxv=-0x3f3f3f3f,minv=0x3f3f3f3f;
    for(int i=1;i<=n;i++)
        minv=min(minv,dp[i][i+n-1]),maxv=max(maxv,g[i][i+n-1]);
    cout<<minv<<endl<<maxv<<endl;
    return 0;
    
}