环形石子合并——区间DP

将 nn 堆石子绕圆形操场排放，现要将石子有序地合并成一堆。

规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。

请编写一个程序，读入堆数 nn 及每堆的石子数，并进行如下计算：

• 选择一种合并石子的方案，使得做 n−1 次合并得分总和最大。
• 选择一种合并石子的方案，使得做 n−1 次合并得分总和最小。

输入格式

第一行包含整数 n，表示共有 n 堆石子。

第二行包含 n 个整数，分别表示每堆石子的数量。

输出格式

输出共两行：

第一行为合并得分总和最小值，

第二行为合并得分总和最大值。

数据范围

1≤n≤200

输入样例：

4
4 5 9 4

输出样例：

43
54

思路：

f[i][j]:左端点为i,右端点为j的区间已经合并，属性：区间的得分

一个大的区间的得分=两个小的区间的得分+这个大区间内的所有石子数

何为环形区间？就只是区间内的第一个数和最后一个数是相邻的。

怎么解决环形问题？输入的时候数组开两倍，在n+1这个位置开始往后重新输入一遍

code：

#include
#include
#include
using namespace std;
 
int n; 
int a[410];
int s[410];
int f[410][410];	//f[i][j]:左端点为i,右端点为j这个区间已经合并完毕的得分 max 
int g[410][410];	//属性:min 
 
int main()
{
	memset(g,0x3f,sizeof g);
	
	
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		a[i+n] = a[i];
		g[i][i] = g[i+n][i+n] = 0;
	}
	
	for(int i=1;i<=2*n;i++) s[i] = s[i-1]+a[i];
	 
	for(int len=2;len<=n;len++)
		for(int i=1;i+len-1<2*n;i++)
		{
			int j = i+len-1;
			
			for(int k=i;k
			{
				f[i][j] = max(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
				g[i][j] = min(g[i][j],g[i][k]+g[k+1][j]+s[j]-s[i-1]);
			}
			
		}
	
	int maxn = -0x3f3f3f3f;
	int minn = 0x3f3f3f3f;
	
	for(int i=1;i<=n+1;i++)
	{
		maxn = max(maxn,f[i][i+n-1]);
		minn = min(minn,g[i][i+n-1]);
	}
	
	cout<
	cout<
	
	return 0;
 }