让AI尝试优化代码时发现的,用上后速度快接近一倍.

#include<bits/stdc++.h>
using namespace std;
const int N=1001;
int a[N*2],sum[N*2];
int f1[N*2][N*2],f2[N*2][N*2];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i+n]=a[i];
		f1[i][i]=f1[i+n][i+n]=0;
		f2[i][i]=f2[i+n][i+n]=0;
	}
	for(int i=1;i<=n*2;i++)sum[i]=sum[i-1]+a[i];
	for(int i=2;i<=n;i++){//长度
		for(int l=1;l<=2*n-i+1;l++){
			int r=l+i-1;
			f1[l][r]=INT_MAX;
			f2[l][r]=0;
			for(int k=0;k<i-1;k++){
				f1[l][r]=min(f1[l][r],f1[l][l+k]+f1[l+k+1][r]+sum[r]-sum[l-1]);
				f2[l][r]=max(f2[l][r],f2[l][l+k]+f2[l+k+1][r]+sum[r]-sum[l-1]);
			}
		}
	}
	int minn=INT_MAX,maxn=0;
	for(int i=1;i<=n;i++){
		minn=min(minn,f1[i][i+n-1]);
		maxn=max(maxn,f2[i][i+n-1]);
	}
	cout<<minn<<"\n"<<maxn;
}