poj 1095 Trees Made to Order 卡特兰数

时间:2023-03-08 17:08:47
poj 1095 Trees Made to Order 卡特兰数

这题用到了卡特兰数,详情见:http://www.cnblogs.com/jackge/archive/2013/05/19/3086519.html

解体思路详见:http://blog.csdn.net/lvlu911/article/details/5425974

代码如下:

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#define ll __int64
#define pi acos(-1.0)
#define MAX 50000
using namespace std;
int an[]={,,,,,,,,,,,,,
,,,,,};
void fun(int n,int k)
{
if(n==){
cout<<'X';
return;
}
int i,sum=;
for(i=;sum<k;i++)
sum+=an[i]*an[n-i-];
i--;
sum-=an[i]*an[n-i-];
k-=sum;
if(i){
cout<<'(';
fun(i,(k-)/an[n-i-]+);
cout<<')';
}
cout<<'X';
if(n-i-){
cout<<'(';
fun(n-i-,(k-)%an[n-i-]+);
cout<<')';
}
}
int main(){
int n,m,sum,i;
while(cin>>n&&n){
sum=;
for(i=;sum<n;i++)
sum+=an[i];
i--;
fun(i,n-sum+an[i]);
cout<<endl;
}
return ;
}