A decorative fence_综合

http://acm.pku.edu.cn/JudgeOnline/problem?id=1037 A decorative fence，这是一道递推的好题啊！

具体的我也不说了，去看解题报告吧。

发现子问题是一个难点，而且进一步的处理也是比较烦的，最好想清楚了再写，不然……

而且输出也很别致。

#include < iostream >
#include < iterator >
using namespace std;

const int N = 21 ; // N
const int M = 21 ; // j
/*
up[i][j]=down[i][i+1-j];
down[i][j+1]=down[i][j]+up[i-1][j]
*/

__int64 down[N][M] = { 0 },up[N][M];

void solve( int n)
{
     int i,j;
    down[ 2 ][ 2 ] = up[ 1 ][ 1 ] = 1 ;
     for (i = 2 ; i <= n; i ++ )
    {
         for (j = 1 ; j < i; j ++ )
            down[i][j + 1 ] = down[i][j] + up[i - 1 ][j];
         for (j = 1 ; j <= i; j ++ )
            up[i][j] = down[i][i + 1 - j];
    }
}

int iV[N];
void goUp( int ,__int64, int );
void goDown( int n,__int64 c, int lowerBound)
{
     if (n == 1 )    {cout << iV[n] << ' ' ;     return ;    }
     int i,j;
     for (i = lowerBound;i <= n;i ++ )
    {
        c -= down[n][i];
         if (c < 1 )
        {
            cout << iV[i] << ' ' ;
             for (j = i;j <= n;j ++ )
                iV[j] = iV[j + 1 ];
            goUp(n - 1 ,c + down[n][i],i - 1 ); // upperbound not neccessary
             break ;
        }
    }
}

void goUp( int n,__int64 c, int upperBound)
{
     if (n == 1 )
    {
        cout << iV[n] << ' ' ;
         return ;
    }
     int i,j;
     for (i = 1 ;i <= upperBound;i ++ )
    {
        c -= up[n][i];
         if (c < 1 )
        {
            cout << iV[i] << ' ' ;
             for (j = i;j < n;j ++ )
                iV[j] = iV[j + 1 ];
            goDown(n - 1 ,c + up[n][i],i);
             break ;
        }
    }
}

void output( int n,__int64 c)
{
     int i,j;
     for (i = 1 ;i <= n;i ++ )
        iV[i] = i;
     if (n == 1 )
    {
        cout << iV[n] << ' ' ;
    }
     for (i = 2 ;i <= n;i ++ )
    {
        c -= up[n][i - 1 ];
         if (c < 1 )
        {
            cout << iV[i - 1 ] << ' ' ;
             for (j = i - 1 ;j < n;j ++ )
                iV[j] = iV[j + 1 ];
            goDown(n - 1 ,c + up[n][i - 1 ],i - 1 );
             break ;
        }
        c -= down[n][i];
         if (c < 1 )
        {
            cout << iV[i] << ' ' ;
             for (j = i;j < n;j ++ )
                iV[j] = iV[j + 1 ];
            goUp(n - 1 ,c + down[n][i],i);
             break ;
        }

    }
}

int main()
{
     int nCase,n;
    __int64 c;
    solve(N - 1 );
    cin >> nCase;
     while (nCase -- )
    {
        cin >> n >> c;
        output(n,c);
        cout << endl;
         /* solve(n,c); */
    }
     return 0 ;
}