20分求助
查看原帖
20分求助
221551
Bker_楼主2022/8/30 00:13

本蒟蒻总是在处理最小值的时候不对 ,求各位神犇们教一教

#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 ;
}
2022/8/30 00:13
加载中...