主要思路

这道题是计数类 DP 中一道非常好的题。

我先来简述一下“试填法”。很多做过数位 DP 的神仙们都可能比较熟悉这样的技巧，一次次相减尝试并统计答案。这就是试填法，特别是在一些递推形式的数位 DP 中会经常简单这样的方法。

那我们开始来分析一下这道题吧。首先，设\(F[i][j][0/1]\)为木板数为\(i\)时，最后放置的木板排名为\(j\)且处于低位（0）或高位（1）。可以写出递推式：

\[ F[i][j][0] = \sum_{h=j}^{i-1} F[i-1][h][1] \\ F[i][j][1] = \sum_{h = 1}^{j-1} F[i-1][h][0] \]

之后，我们可以试图找出第一块木板的排名，设\(last\)为上一块木板的排名，\(k\)为上一块木板是否为高位（0/1）。通过枚举高度并试填：

• 当枚举到的方案数小于目前的方案余量，余量减去并继续枚举。
• 当方案数大于方案余量，记下状态并跳出。

对于之后的\([2,n]\)块木板，道理是一样的。需要注意的是，我们的枚举顺序从\(n\)到\(1\)，保证完整性。

代码

// POJ1037.cpp
#include <cstdio>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;
ll n, m, T, f[25][25][2];
bool vis[25];
void initialize()
{
    f[1][1][0] = f[1][1][1] = 1;
    for (int i = 1; i <= 20; i++)
        for (int j = 1; j <= i; j++)
        {
            for (int k = j; k <= i - 1; k++)
                f[i][j][0] += f[i - 1][k][1];
            for (int k = 1; k <= j - 1; k++)
                f[i][j][1] += f[i - 1][k][0];
        }
}
int main()
{
    scanf("%d", &T);
    initialize();
    while (T--)
    {
        memset(vis, 0, sizeof(vis));
        scanf("%lld%lld", &n, &m);
        // to determine the first condition;
        ll last, k;
        for (int j = 1; j <= n; j++)
        {
            if (f[n][j][1] >= m)
            {
                last = j, k = 1;
                break;
            }
            else
                m -= f[n][j][1];
            if (f[n][j][0] >= m)
            {
                last = j, k = 0;
                break;
            }
            else
                m -= f[n][j][0];
        }
        vis[last] = true;
        printf("%lld", last);
        for (int i = 2; i <= n; i++)
        {
            k ^= 1;
            int j = 0;
            for (int len = 1; len <= n; len++)
            {
                if (vis[len])
                    continue;
                j++;
                if ((k == 1 && len > last) || (k == 0 && len < last))
                    if (f[n - i + 1][j][k] >= m)
                    {
                        last = len;
                        break;
                    }
                    else
                        m -= f[n - i + 1][j][k];
            }
            printf(" %lld", last);
            vis[last] = true;
        }
        puts("");
    }
    return 0;
}