http://poj.org/problem?id=1095
先打个表 然后dfs一下
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<cstring>
#include<set>
#include<cmath>
#include<algorithm>
#define LL long long
using namespace std;
const int N=25;
int a[N];
void begin()
{
a[0]=1;
a[1]=1;
for(int i=2;i<N;++i)
{
a[i]=0;
for(int l=0;l<i;++l)
{
a[i]+=(a[l]*a[i-l-1]);
}
}
}
int I;
void dfs(int k,int s)
{
if(k==1)
{
printf("X");
return ;
}
int l;
int sum=0;
for(l=0;l<k;++l)
{
sum+=a[l]*a[k-l-1];
if(sum>=s)
{
sum-=a[l]*a[k-l-1];
break;
}
}
sum=s-sum;
int w=sum/a[k-l-1];
if(sum%a[k-l-1])
++w;
if(l>0)
{
printf("(");
dfs(l,w);
printf(")");
}
printf("X");
if(k-l-1>0)
{
printf("(");
dfs(k-l-1,sum-(w-1)*a[k-l-1]);
printf(")");
}
}
int main()
{
//freopen("data.txt","r",stdin);
begin();
int n;
while(scanf("%d",&n)!=EOF)
{
if(n==0)
break;
int sum=0;I=0;
for(int i=1;i<=N;++i)
{
sum+=a[i];
if(sum>=n)
{
dfs(i,n-(sum-a[i]));
break;
}
}
printf("\n");
}
return 0;
}
