感谢所有AC

传送门

思路

       经典的环形dp，由区间dp的弱化版转变而来。

       对于环形，需要破环成链。某两个石子之间必然存在一个断点，即断点两边的石子永远不会合并。从环中取链进行dp的时间复杂度大，不妨考虑把原来的序列扩增成两倍，这样一来，每一种链的可能性都存在于这个2N的序列中。剩下的步骤就和弱化版的相同了，枚举区间长度，枚举区间，枚举断点进行转移，最后扫一遍所有链找到最值。

代码

#include
#define maxn 207
using namespace std;
int a[maxn][maxn], f1[maxn][maxn], f2[maxn][maxn], n;
//破环成链，两倍空间
int ans1 = INT32_MAX, ans2 = INT32_MIN;
int main(void)
{
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i][i];
		a[n + i][n + i] = a[i][i];
	}
	for (int L = 2; L <= n; L++)
	{
		for (int i = 1; i <= 2 * n - L + 1; i++)//L长度下有（2*n-L+1）条链
		{
			int l = i, r = i + L - 1;
			for (int j = 1; j < L; j++)//和弱化版一样的枚举断点
			{
				a[l][r] = a[l][l + j - 1] + a[l + j][r];//可以在循环外部前缀和实现
				//f1规划最小值，转移时需要特殊处理
				if (f1[l][r] == 0)
					f1[l][r] = f1[l][l + j - 1] + f1[l + j][r] + a[l][r];
				else
					f1[l][r] = min(f1[l][r], f1[l][l + j - 1] + f1[l + j][r] + a[l][r]);
				f2[l][r] = max(f2[l][r], f2[l][l + j - 1] + f2[l + j][r] + a[l][r]);
			}
		}
	}
	//所有链中找答案
	for (int i = 1; i <= n; i++)
		ans1 = min(ans1, f1[i][i + n - 1]), ans2 = max(ans2, f2[i][i + n - 1]);
	cout << ans1 << endl << ans2 << endl;
	return 0;
}