PKU 1037 A decorative fence - kusano

分からないのでカンニング。なるほど、途中まで板の長さを決めたときに残りの板の選び方が何通りあるかを先にDPで求めておくのか。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    const int M = 20;

    //  [i][j][k]　残りi枚の板をジグザグに並べる場合の数
    //  ただし、左隣の板とi枚の板を短い順に並べると左隣の板はj番目
    //  また、k=0ならば左隣の板より長い板を次に、k=1ならば短い板を次に
    long long T[M+1][M+1][2] = { { { 0 } } };
    T[0][0][0] = T[0][0][1] = 1;

    for ( int i=1; i<=M; i++ )
    for ( int j=0; j<=i; j++ )
    {
        for ( int k=0; k<j; k++ )  T[i][j][1] += T[i-1][k][0];
        for ( int k=j; k<i; k++ )  T[i][j][0] += T[i-1][k][1];
    }

    int K;  cin >> K;
    for ( int k=0; k<K; k++ )
    {
        int N;  cin >> N;
        long long C;  cin >> C;
        C--;

        vector<int> F( N );
        vector<bool> use( N );

        for ( int n=0; n<N; n++ )
        {
            long long c = 0;

            int t;
            for ( t=0; t<N; t++ )
            if ( ! use[t]  &&
                 ( n <= 1  ||  (F[n-1]-F[n-2])*(F[n-1]-t) > 0 ) )
            {
                int a = 0;
                for ( int i=0; i<N; i++ )
                    if ( ! use[i]  &&  i < t )
                        a++;
                long long x = 0;
                if ( n > 0  &&  F[n-1] > t  ||  n == 0 )  x += T[N-n-1][a][0];
                if ( n > 0  &&  F[n-1] < t  ||  n == 0 )  x += T[N-n-1][a][1];

                if ( c + x > C )
                    break;

                c += x;
            }

            F[n] = t;
            use[t] = true;
            C -= c;
        }

        for ( int i=0; i<N; i++ )
            cout << (i>0?" ":"") << F[i]+1;
        cout << endl;
    }
}