复习(du) 这道题,发现思想真不错
当时背板子打下来的
要下晚自习了,明天更注释吧
#include<iostream> #include<queue> #include<cmath> #include<cstdio> #include<cstring> using namespace std; int f2[200][200],f1[200][200]; int s[1008],n; int a[1008]; int ans1,ans2; int sum(int left,int right) { return s[right]-s[left-1]; } int main() { memset(f1,-1,sizeof(f1)); memset(f2,0x3f,sizeof(f2)); int i,j; scanf("%d ",&n); for(i=1;i<=n;i++) { scanf("%d",&a[i]); s[i]=a[i]+s[i-1]; a[i+n]=a[i]; f1[i][i]=0; f2[i][i]=0; } for(i=n+1;i<=n*2;i++) { s[i]=a[i]+s[i-1]; f1[i][i]=0; f2[i][i]=0; } int l,k; for(l=2;l<=n;l++) for(i=1;i<=2*n-l;i++) { j=i+l-1; for(k=i;k<j;k++) { f1[i][j]=max(f1[i][k]+f1[k+1][j],f1[i][j]); f2[i][j]=min(f2[i][k]+f2[k+1][j],f2[i][j]); } f1[i][j]+=sum(i,j); f2[i][j]+=sum(i,j); } ans1=-1; ans2=0x3f3f3f3f; for(i=1;i<=n;i++) { ans1=max(ans1,f1[i][i+n-1]); ans2=min(ans2,f2[i][i+n-1]); } printf("%d\n%d ",ans2,ans1); return 0; }
原文:https://www.cnblogs.com/zsx6/p/11054832.html