区间dp-环形石子合并

传送门https://www.luogu.com.cn/problem/P1880

相对于弱化版     这里需要注意（不只是因为环形）

1. 1.环形做法（环成链）
2. 2.前缀和维护（不太好计算区间和）
3. 3.memset需要用cstring头文件
4. 4.对f【0】【0】的操作

文字无力，见代码

#include<iostream>
#include<cstring>//别忘了，因为这个WA一发
using namespace std;
const int N=305;
int f[N][N];
int g[N][N];//分别记录大小数组
int s[N];//前缀和
int a[N];
int minn=1e9;
int maxn=-1e9;
#define inf 0x3f

int main(){
	memset(f,0x3f,sizeof f);//先全部设为最大，这样方便后面操作
	memset(g,0,sizeof g);//不会是负数，0即可
	int n;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];f[i][i]=0,g[i][i]=0;//前缀和和前置操作  （f【0】【0】）
	}
	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<j;++k){//从哪里开始分开
				f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
				g[i][j]=max(g[i][j],g[i][k]+g[k+1][j]+s[j]-s[i-1]);
                
                minn=min(minn,f[i][i+n-1]);//这里如果没有被操作，将会一直是最大值
                maxn=max(maxn,g[i][i+n-1]);
			}
		}
	}
	cout<<minn<<endl<<maxn;
	
	return 0;
}