本题为石子合并的升级版，变成了环形合并。

首先可以将环变成链，也就是将环拆开延长一倍即可。$a[n + i] = a[i];$

设$f[i][j]$为区间$i$到$j$合并的最小值，$g[i][j]$为区间i到j合并的最大值。

转移方程以及状态初始化都同基础版本，唯一要注意，区间长度仍然是2到n的枚举，

但是左右端点是延长了的。

最后最小值自然是枚举$i$，求$f[i][i+n-1]$的最小值。最大值同理。

#include <bits/stdc++.h>
using namespace std;
int n, a[805], sum[805], f[805][805], g[805][805];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	memset(f, 0x3f, sizeof(f));
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		a[n + i] = a[i];
	}
	for (int i = 1; i <= n * 2; i++)
	{
		sum[i] = sum[i - 1] + a[i];
		f[i][i] = 0;
	}
	for (int len = 2; len <= n; len++)
	{
		for (int i = 1; i + len - 1 <= n * 2; 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] + sum[j] - sum[i - 1]);
				g[i][j] = max(g[i][j], g[i][k] + g[k + 1][j] + sum[j] - sum[i - 1]);
			}
		}
	}
	int ans1 = 0x3f3f3f3f, ans2 = 0;
	for (int i = 1; i <= n; i++)
	{
		ans1 = min(ans1, f[i][i + n - 1]);
		ans2 = max(ans2, g[i][i + n - 1]);
	}
	cout << ans1 << "\n"
		 << ans2;
	return 0;
}