区间dp将环转化成链

#include <bits/stdc++.h>
using namespace std;
/* 区间dp的动态转移方程的大多公式
dp[i][j]=min/max(dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
sum[]为前缀和方便算区间的总和 

当dp中出现环 
1.由于石子围成一个环，我们可以枚举分开的位置，将这个换转化成
一个链，由于要枚举n次，最终时间复杂度为O(n^4);
2.我们也可以将这条链延长2倍变成2n堆其中第i堆与第n+i堆相同，用
动态规划求解后，取f(1,n)f(2,n+1)..f(n-1,2n-2);的最优解
这里我用的是第二个方法
大意就是len=n时可以为
双倍后的ABCDEABCD变为
ABCDE----
-BCDEA---
--CDEAB--
---DEABC-
----EABCD
等情况这样就可以将环转化成我们比较好理解的环了
*/ 
const int maxn=1e6+9;
int dp[209][209],a[209],dp1[209][209];
int sum[209]; 
int main(){
	//freopen("xx.in","r",stdin);
	//freopen("xx.out","w",stdout);
    int n;
	cin >> n;
	for(int i=1;i<=n;i++)cin >> a[i];
	for(int i=1;i<=(n<<1)-1;i++){
		a[i+n]=a[i];
		sum[i]=sum[i-1]+a[i]; 
        //cout <<sum[i]<<" ";
	} 
    int mi=maxn,mx=-maxn;
	for(int l=2;l<=n;l++){
		//l为区间长度 同理也是每次合并的最优解 
		for(int i=1,j=l;j<=(n<<1)-1;i++,j++){
			dp[i][j]=maxn;
			//这个子区间的石子堆 
			for(int k=i;k<j;k++){
				dp[i][j]=min(dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1],dp[i][j]);
                dp1[i][j]=max(dp1[i][k]+dp1[k+1][j]+sum[j]-sum[i-1],dp1[i][j]);
		        if(l==n){mi=min(dp[i][j],mi);mx=max(dp1[i][j],mx);}
		}
	}
    }
	cout <<mi<<endl<<mx;
	return 0;
}