洛谷 P1880 [NOI1995]石子合并

这道题是之前石子合并的加强板

https://blog.csdn.net/qq_34416123/article/details/81913341

不同在于是一个环

处理方法就是把数组 
乘以2，枚举起点转化成链。
以后这种环的问题应该都可以这样来转化。

数组空间不要忘了乘以2

然后要注意区间从长度为2开始，初始化为最大或最小
注意这里的得分是合并之后的得分，所以单独一堆是没有得分的。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
const int MAXN = 212;
int f1[MAXN][MAXN], f2[MAXN][MAXN], a[MAXN], n;
 
int main()
{
	scanf("%d", &n);
	_for(i, 1, n)
	{
		int x;
		scanf("%d", &x);
		a[i] = a[i-1] + x;
	}
	_for(i, 1, n) a[n + i] = a[n] + a[i];
		
	int ans1 = 0, ans2 = 1e8;
	_for(d, 1, n)
		for(int st = 1; st + d - 1 <= 2 * n; st++)
		{
			int i = st, j = st + d - 1;
			f1[i][j] = 0;
			f2[i][j] = 1e8;
			REP(k, i, j)
			{
				f1[i][j] = max(f1[i][j], f1[i][k] + f1[k+1][j] + (a[j] - a[i-1]));
				f2[i][j] = min(f2[i][j], f2[i][k] + f2[k+1][j] + (a[j] - a[i-1]));
			}
			if(d == n)
			{
				ans1 = max(ans1, f1[i][j]);
				ans2 = min(ans2, f2[i][j]);
			}
		}
	printf("%d
%d
", ans2, ans1);
	
	return 0;
}