60分代码,错了第3和第5点
#include<bits/stdc++.h>
using namespace std;
int n,a[105],f[205][205],dp[205][205];
int ans1,ans2=1e9;
int main(){
cin>>n;
memset(dp,0x7f,sizeof(dp));
memset(f,-0x7f,sizeof(f));
for(int i=1;i<=n;i++){
cin>>a[i];
a[i+n]=a[i];
dp[i][i]=dp[i+n][i+n]=0;
f[i][i]=f[i+n][i+n]=0;
}
for(int i=1;i<=2*n;i++) a[i]+=a[i-1];
for(int len=1;len<n;len++)
for(int i=1;i+len<=2*n;i++){
int j=i+len;
for(int k=i;k<j;k++){
f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+a[j]-a[i-1]);
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+a[j]-a[i-1]);
}
}
for(int i=1;i<=n;i++){
ans1=max(ans1,f[i][i+n-1]);
ans2=min(ans2,dp[i][i+n-1]);
}
cout<<ans2<<"\n"<<ans1;
return 0;
}
测试点3: 输入:
78
4 4 10 13 7 1 16 7 0 7 19 7 9 14 18 1 5 17 1 8 11 19 15 18 11 12 2 3 7 1 13 0 17 10 2 5 1 7 1 10 7 0 12 10 9 10 9 18 11 11 7 8 6 10 7 18 1 11 2 3 18 9 17 17 10 14 16 1 4 7 1 5 11 3 13 17 7 0
标准输出:
4084
28949
我的输出:
4084
28949