환상 dp 템플릿 로곡 P1880 석자 합병 문제풀이

환상 dp 템플릿 로곡 P1880 석자 합병 문제풀이

#include
using namespace std;
int n,minn,maxx,f1[300][300],f2[300][300],num[300];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
	 	scanf("%d",&num[i]);
	 	num[i+n]=num[i];//    dp   ，             ，         ，     
	}
	for(int i=1;i<=2*n;i++){
		num[i]=num[i]+num[i-1];
	}	
	
	for(int r=2;r<=n;r++){//   r       ，     i   i+r-1 ，(   ，   ) 
		for(int i=1;i<=2*n-r+1;i++){
			int j=i+r-1;//  i++，  ++，  --,        sumj-sum(i-1) 
			f1[i][j]=f1[i+1][j]+num[j]-num[i-1];
			f2[i][j]=f2[i+1][j]+num[j]-num[i-1];
			for(int k=i;k<j;k++){
			// i,j     dp   
			f1[i][j]=max(f1[i][j],f1[i][k]+f1[k+1][j]+num[j]-num[i-1]); //k           
			f2[i][j]=min(f2[i][j],f2[i][k]+f2[k+1][j]+num[j]-num[i-1]);
			 
		} 
	} 
} 
	 maxx=f1[1][n],minn=f2[1][n];
	for(int i=2;i<=n;i++){
		maxx=max(f1[i][i+n-1],maxx);
		minn=min(f2[i][i+n-1],minn);
	} 
	printf("%d
%d",minn,maxx);
	return 0;
}

제목 전송문 본낙곡 블로그 전송문