$\LARGE\color{orange}{刷题日记(算法提高课)}$

这道题跟 AcWing 282. 石子合并 基本很类似

原题是链状的，本题是环状的

根据环的断开方式，可以转换成 $n$ 条链，如果对每条链都用一次上一题的方法的话，那么时间复杂度会到达 $O(n^4)$

这里我们给出处理「环」的一般思路

题目给了 $n$ 个元素，我们可以在后面再补上 $n$ 个一模一样的元素，使得总元素数达到 $2n$

这样从环状分解出来的 $n$ 个长度为 $n$ 的区间，都可以在这样一条长度为 $2n$ 的链上面进行表示，即区间 $[i,\ i+n-1]$

因此我们对这条长度为 $2n$ 的链做一次区间 DP ，总时间复杂度不过才 $O(n^3)$

需要注意的是，我们的区间长度最大枚举到 $n$ ，右端点却最大可以到 $2n$

我们预处理出来所有 $f[l][r]$ 的值，然后取区间 $[i,\ i+n-1]$ 的最大最小值即可

完整代码：

#include <iostream>
#include <cstring>

using namespace std;

const int N = 410, INF = 0x3f3f3f3f;

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

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> q[i];
        q[i + n] = q[i];
    }
    for(int i = 1; i <= n * 2; i++)
        s[i] = s[i - 1] + q[i];

    memset(f, -INF, sizeof f);
    memset(g, INF, sizeof g);
    for(int len = 1; len <= n; len++)
    {
        for(int l = 1; l + len - 1 <= n * 2; l++)
        {
            int r = l + len - 1;
            if(len == 1)
                f[l][r] = g[l][r] = 0;
            else
            {
                for(int k = l; k < r; k++)
                {
                    f[l][r] = max(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
                    g[l][r] = min(g[l][r], g[l][k] + g[k + 1][r] + s[r] - s[l - 1]);
                }
            }
        }
    }

    int maxv = -INF, minv = INF;
    for(int i = 1; i <= n; i++)
    {
        maxv = max(maxv, f[i][i + n - 1]);//这里需要减一，以保证区间长度为n
        minv = min(minv, g[i][i + n - 1]);
    }

    cout << minv << endl << maxv << endl;

    return 0;
}