#include<iostream> #include<cstring> int f[1000][1000],s[10000],a[10000]; int k,n,maxn,miny=100000000; using namespace std; int main() { cin>>n; memset(f,0x3f,sizeof(f)); for(int i=1;i<=n;i++) { cin>>a[i]; s[i]=s[i-1]+a[i]; f[i][i]=0; } for(int i=n+1;i<2*n;i++) { a[i]=a[i-n]; s[i]=s[i-1]+a[i]; f[i][i]=0; } // len+l-1=j //j-l=len-1 for(int len=2;len<=n;len++) { for(int l=1;len+l-1<=2*n;l++) { int r=l+len-1; 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]); } } miny=f[1][n]; for(int i=2;i<=n;i++) { miny=min(miny,f[i][i+n-1]); } // cout<<f[1][n]<<endl; cout<<miny<<endl; memset(f,0,sizeof(f)); for(int len=2;len<=2*n;len++) { for(int l=1;len+l-1<=2*n;l++) { int r=l+len-1; for(int k=l;k<r;k++) f[l][r]=max(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]); } } // cout<<f[1][n]; for(int i=1;i<=n;i++) { maxn=max(maxn,f[i][i+n-1]); } cout<<maxn; return 0;
}
标签:10000,int,石子,合并,环形,include,1000 From: https://www.cnblogs.com/xdzxsuming/p/16725897.html