4580452_ac_0ms_260k.cpp

部分PKU上的源码

#include <iostream>
using namespace std;
 
const int MAX = 21;
 
__int64 W[MAX][MAX];
__int64 M[MAX][MAX];
int used[MAX];         //用于输出时判断木条的使用情况
__int64 c;
int n;
 
void Input ()
{
        scanf("%d%I64d", &n, &c);
}
 
//利用递归进行初始化
__int64 getDown (int x, int n);
__int64 getUp (int x, int n);
 
__int64 getDown (int x, int n)
{
        if ( W[x][n] != -1 )
               return W[x][n];
        int i;
        __int64 ans;
        ans = 0;
        for (i=1; i<x; i++)
               ans += getUp (i, n-1);
 
        return ( W[x][n] = ans );
}
 
__int64 getUp (int x, int n)
{
        if ( M[x][n] != -1 )
               return M[x][n];
 
        return ( M[x][n] = getDown(n-x+1, n) );
}
 
void Init ()
{
        int i, j;
 
        memset(W, -1, sizeof(W));
        memset(M, -1, sizeof(M));
 
        for (i=1; i<=MAX; i++)
               W[1][i] = 0;
        W[1][1] = 1;
        M[1][1] = 1;
        W[1][2] = 0;
        M[1][2] = 1;
        W[2][2] = 1;
        M[2][2] = 0;
 
        for (i=3; i<=MAX; i++)
        {
               for (j=1; j<=i; j++)
               {
                       getDown(j, i);
                       getUp(j, i);
               }
        }
 
}
 
//子问题中，1～k范围内第x根木条实际的位置
void Output (int x, int k)
{       
        int i;
        do
        {
               for (i=1; i<=k; i++)
               {
                        //若1～k中有以前已确定的木条，并且x木条比已确定的木
                        //条长度要长，那么x木条的长度应加1
                       if ( used[i] && x >= i )
                       {
                               x++;
                               k++;
                       }
               }
        } while ( used[x] );
        if ( k > 1 )
               printf("%d ", x);
        else
               printf("%d", x);
        used[x] = 1;
        
}
 
void Solve ()
{
        int up, i, first;
        up = 1;
        i = 1;
        first = 1;
        memset(used, 0, sizeof(used));
 
        while ( n > 0 )
        {
               if ( up == 1 )
               {
                       if ( c > M[i][n] )
                       {
                               if ( first )   //是否是在查找第1根木条
                               {
                                      up = !up;
                               }
                               c -= M[i][n];
                               i++;
                       }
                       else
                       {
                               Output(i, n);
                               first = 0;
                               //i = 1;
                               up = !up;
                               n--;
                       }
               }
               else
               {
                       if ( c > W[i][n] )
                       {
                               if ( first )
                               {
                                       up = !up;
                               }
                               c -= W[i][n];
                               if ( !first )
                               {
                                      i ++;
                               }
                       }
                       else
                       {
                               Output(i, n);
                               first = 0;
                               up = !up;
                               n--;
                               i = 1;
                       }
               }
        }
 
        printf("\n");
}
 
int main ()
{
        int test;
        cin>>test;
        Init ();
        while ( test-- )
        {
               Input ();
               Solve ();
        }
 
        return 0;
}