POJ 1095 Trees Made to Order 카트란 수 및 재 귀 분할

전재 출처 를 밝 혀 주 십시오.감사합니다.http://blog.csdn.net/ACM_cxlove?viewmode=contents           by---cxlove
제목 링크http://poj.org/problem?id=1095
debug 에서 알 이 깨 질 때 까지 의 문 제 는 원래 카 틀 랜 드 수 를 잘 알 고 있 었 는데,결국 카 틀 랜 드 수 부분 은 매우 물 러 서 계속 디 버 깅 을 하고 있 었 다.
카 틀 란 수 를 미리 처리 한 후에 현재 몇 개의 노드 로 구 성 된 이 진 트 리 를 내 놓 을 수 있 고 현재 노드 의 모든 정렬 에서 의 순위 도 알 수 있 습 니 다.
그 다음 에 재 귀 를 시작 하고 오른쪽 나무 부터 매 거 를 시작 하여 좌우 나무의 노드 개 수 를 판단 하고 재 귀 를 한다.debug 반나절 의 원인 은 제목 을 읽 지 못 했 기 때 문 입 니 다.정렬 관계 가 잘못 되 었 습 니 다.멘 붕 입 니 다.
영 어 를 잘 못 하 는데,과연 다 칠 수 없 으 니,다음 에 문 제 를 읽 을 때 는 반드시 주의해 야 한다.

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL __int64
using namespace std;
LL c[30]={1};
//       
void Init(){
	for(int i=1;i<=25;i++){
		c[i]=c[i-1]*(4*i-2)/(i+1);
	}
}
//  k        cnt     
void slove(int k,int cnt){
	//      ，    
	if(k==1){
		printf("X");
		return;
	}
	//     ，     
	if(cnt<=c[k-1]){
		printf("X");
		printf("(");
		slove(k-1,cnt);
		printf(")");
	}
	//     ，     
	else if(cnt>c[k]-c[k-1]){
		printf("(");
		slove(k-1,cnt-(c[k]-c[k-1]));
		printf(")");
		printf("X");
	}
	else{
		int t=k-1,m;
		//             ，    
		for(int i=t;i>=0;i--){
			if(c[i]*c[t-i]<cnt)
				cnt-=c[i]*c[t-i];
			else{
				m=i;
				break;
			}
		}
		printf("(");
		//     
		slove(t-m,cnt/c[m]+(cnt%c[m]!=0));
		printf(")X(");
		//     
		slove(m,(cnt-1)%c[m]+1);
		printf(")");
	}
}
int main(){
	int n,m;
	Init();
	while(scanf("%d",&n)!=EOF&&n){
		for(int i=1;;i++){
			if(n>c[i])
				n-=c[i];
			else{
				m=i;
				break;
			}
		}
		slove(m,n);
		printf("
");
	}
	return 0;
}