本蒟蒻总是在处理最小值的时候不对 ,求各位神犇们教一教
#include <iostream>
using namespace std;
const int maxn = 1001 ;
int n , a[maxn] , w[maxn] , f1[maxn][maxn] , f2[maxn][maxn] ;
int main(){
scanf("%d" , &n) ;
for(int i = 1 ; i <= n ; i++){
scanf("%d" , &a[i]) ;
a[i + n] = a[i] ;
}
for(int i = 1 ; i <= n + n ; i++){
w[i] = w[i - 1] + a[i] ;
f1[i][i] = f2[i][i] = 0 ;
}
for(int len = 2 ; len <= n ; len++)
for(int i = 1 ; i <= n + n - len + 1 ; i++){
int j = i + len - 1 ;
f1[i][j] = 0x3fff ;
for(int k = i ; k < j ; k++){
f1[i][j] = min(f1[i][j] , f1[i][k] + f1[k + 1][j] + w[j] - w[i - 1]) ;
f2[i][j] = max(f2[i][j] , f2[i][k] + f2[k + 1][j] + w[j] - w[i - 1]) ;
}
}
int ans = 0x3fff ;
for(int i = 1 ; i <= n ; i++)
ans = min(ans , f1[i][i + n - 1]) ;
printf("%d\n" , ans);
printf("%d" , f2[1][n]) ;
return 0 ;
}