题解 | #石子合并#E

因为石子摆在圆形操场的四周，是一个环，我们可以利用a[i+n]=a[i]，把环拆成链。n堆石子中挑选任意区间。f[l][r]表示从l到r合并成一堆的最小代价。 先把[l,r]切分为两部分,[l,k]和[k+1,r],k是切分点。再把两部分合并在一起消耗的代价就是从[l,r]所有的质量之和。用前缀和求区间和是s[r]-s[l-1]. 转移方程：f[L,K]+f[K+1,R]+s[R]-s[L-1]->f[L,R] 计算：f[L,R]=min(f[L,R],f[L,K]+f[K+1,R]+s[R]-s[L-1]) 最大值和最小值同理

#include<bits/stdc++.h>
using namespace std;
int n;
int a[300],s[300];//s记录前缀和 
int f[300][300];//f[l][r]指从l到r合并成一堆的最小代价
int g[300][300];//最大代价 
const int oo=0x3f3f3f3f;
int main()
{
	memset(g,0,sizeof(g));
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		a[i+n]=a[i];//环拆成链 
	}
	for(int i=1;i<=2*n;i++)
	{
		s[i]=s[i-1]+a[i];
	 } 
	for(int len=2;len<=n;len++)//阶段：枚举区间长度 
	{
		for(int l=1,r=l+len-1;l<=2*n-1 && r<=2*n-1;l++,r++)//状态：枚举区间起点 ,终点 
		{
			f[l][r]=oo;
			for(int k=l;k<r;k++)//决策：枚举分割点 
			{
				f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
				g[l][r]=max(g[l][r],g[l][k]+g[k+1][r]+s[r]-s[l-1]);
			}
		} 
	}
	int minans=oo,maxans=0;
	for(int i=1;i<=n;i++)
	{
		minans=min(minans,f[i][i+n-1]);
		maxans=max(maxans,g[i][i+n-1]);
	}
	cout<<minans<<endl<<maxans;
	return 0;
 }