#include<cstdio>
#include<iostream>
using namespace std;
int a[105],sum[105],f1[205][205],f2[205][205];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
a[i+n]=a[i];
}
for(int i=1;i<=2*n;i++){
sum[i]=sum[i-1]+a[i];
f1[i][i]=f2[i][i]=0;
}
for(int i=1;i<2*n;i++)
for(int j=i+1;j<=2*n;j++){
f2[i][j]=10000000;
for(int k=i;k<j;k++){
f1[i][j]=max(f1[i][j],f1[i][k]+f1[k+1][j]+sum[j]-sum[i-1]);
f2[i][j]=min(f2[i][j],f2[i][k]+f2[k+1][j]+sum[j]-sum[i-1]);
}
printf("%d %d %d\n",i,j,f2[i][j]);
}
int maxn=0,minn=100000000;
for(int i=1;i<=n;i++){
maxn=max(maxn,f1[i][i+n-1]);
minn=min(minn,f2[i][i+n-1]);
}
printf("%d\n",minn);
printf("%d\n",maxn);
return 0;
}
by Bro_wang @ 2019-02-03 16:04:15
初始值设置的不够大?
或者你可以尝试一下用memset设置f2到最大值
by CeLaMbDa @ 2019-02-03 16:07:15
```cpp
include<cstdio>
include<iostream>
using namespace std; int a[105],sum[105],f1[205][205],f2[205][205]; int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
a[i+n]=a[i];
}
for(int i=1;i<=2*n;i++){
sum[i]=sum[i-1]+a[i];
f1[i][i]=0, f2[i][j]=10000000;
}
for(int i=1;i<2*n;i++)
for(int j=i+1;j<=2*n;j++){
f2[i][j]=10000000;
for(int k=i;k<j;k++){
f1[i][j]=max(f1[i][j],f1[i][k]+f1[k+1][j]+sum[j]-sum[i-1]);
f2[i][j]=min(f2[i][j],f2[i][k]+f2[k+1][j]+sum[j]-sum[i-1]);
}
printf("%d %d %d\n",i,j,f2[i][j]);
}
int maxn=0,minn=100000000;
for(int i=1;i<=n;i++){
maxn=max(maxn,f1[i][i+n-1]);
minn=min(minn,f2[i][i+n-1]);
}
printf("%d\n",minn);
printf("%d\n",maxn);
return 0;
}
```
这样试一下?
by CeLaMbDa @ 2019-02-03 16:08:24