poj 1095 Trees Made to Order 夜

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;
}