$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

求最小值的思路：

• $1. 状态表示$
  $集合：区间[l,r]内的石子合并后的得分$
  $属性：\min$

• $2. 状态转移$
  $f[l][r]=\min\{f[l][k]+f[k+1][r]+s[r]-s[l-1]\}\ (l\le k < r)$

本题思路：
$环形石子合并的最小值=\min\{f[i][i+n-1]\}\ (1\le i\le n)$
$环形石子合并的最大值=\max\{g[i][i+n-1]\}\ (1\le i\le n)$

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 410, INF = 0x3f3f3f3f;

int n;
int a[N],s[N];
int f[N][N],g[N][N];

int main()
{
    cin>>n;

    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        a[i+n]=a[i]; //再加上一条链
    }

    for(int i=1;i<=n*2;i++) s[i]=s[i-1]+a[i]; //前缀和

    for(int len=2;len<=n;len++) //枚举区间长度，区间长度为 1 的时候不需要合并
        for(int l=1;l+len-1<=n*2;l++) //枚举左端点
        {
            int r=l+len-1; //右端点
            f[l][r]=INF;
            for(int k=l;k<r;k++) //枚举该区间的分界点
            {
                f[l][r]=min(f[l][r],f[l][k]+f[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 minv=INF,maxv=-INF;
    for(int i=1;i<=n;i++)
    {
        minv=min(minv,f[i][i+n-1]);
        maxv=max(maxv,g[i][i+n-1]);
    }

    cout<<minv<<'\n'<<maxv<<endl;

    return 0;
}