『计数DP·输出方案』Decorative Fence

$$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{m}$$

理查德刚刚完成了新房子的建造。现在房子唯一遗漏的是一个可爱的小木栅栏。他不知道如何制作木栅栏，所以他决定订购一个。不知怎的，他得到了ACME Fence Catalogue 2002，这是可爱的小木栅栏的终极资源。在阅读了他已经知道的序言后，是什么让一个小木栅栏变得可爱。

木栅栏由N个木板组成，垂直排成一排。当且仅当满足以下条件时，栅栏看起来很可爱：

木板具有不同的长度，即1,2，… 。。，N木板长度单位。

每个有两个邻居的木板要么大于它的每个邻居，要么小于它们中的每一个。（注意，这会使围栏的顶部交替上升和下降。）

接下来，我们可以用N个木板作为排列a1，…来描述每个可爱的栅栏。。。，数字1的aN ,. 。。，N使得（任何i; 1 < i < N）（ai-ai-1）*（ai-ai + 1）> 0，反之亦然，每个这样的排列描述了可爱的围栏。
很明显，有许多不同的可爱的木栅栏由N木板制成。为了将一些订单带入他们的目录，ACME的销售经理决定以下列方式订购它们：围栏A（由排列a1，…，aN表示）在围栏B之前的目录中（由b1，…表示）。 …，bN）当且仅当存在这样的i时，（任何j < i）aj = bj和（ai < bi）。（另外要确定，目录中较早的两个围栏中的哪一个，采取相应的排列，找到它们不同的第一个位置并比较这个地方的值。）所有带N个木板的可爱围栏都有编号（从1）按照它们出现在目录中的顺序。该号码称为其目录号。

在仔细检查了所有可爱的小木栅栏后，理查德决定订购其中一些。对于他们每个人，他都注意到了木板的数量和目录号。后来，当他遇到他的朋友时，他想向他们展示他订购的围栏，但他在某处遗失了目录。他唯一得到的就是他的笔记。请帮助他找出他的围栏怎么样。

$$\mathrm{S}\mathrm{o}\mathrm{l}\mathrm{u}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$$

我们可以计算出某一块木块对应排名的方案数，如果方案数大于m说明方案一定在这里，用m减去这些方案数，进行下一排名的查找。这是我们对应的解题策略。

我们设$f[i][j][0/1]$表示用了$i$块木块，第i块木块在这里的相对排名为$j$，处于下面/上面的方案数。

那么可以很容易得到状态转移方程：$$f[i][j][0]=\sum _{k=j}^{i?1}f[i?1][k][1]$$
$$f[i][j][1]=\sum _{k=1}^{j?1}f[i?1][k][0]$$
注意第一个状态转移方程的下界是$j$，因为在这里我们在乎的是相对排名，插入的新木板排名为$j$，那么比它小的原来有$j?1$个，剩下的都是比它要大的，因此至少要排名为j的才能满足条件。

然后我们再考虑如何去拼凑答案。

对于第一位，我们需要特殊考虑.从小到大枚举j，先判断$f[1][j][1]$是否合法，再判断$f[1][j][0]$是否合法。因为显然前者的字典序小于后者。

后面对于每一位，我们得到j的时候不能用具体排名而应该用相对排名。具体看实现。

$\mathrm{C}\mathrm{o}\mathrm{d}\mathrm{e}$

#include <cstdio>
#include <iostream>#define int long longusing namespace std;
const int N = 30;int n, m;
int f[N][N][2];void DP(void)
{
    f[1][1][0] = f[1][1][1] = 1;for (int i=2;i<=20;++i)for (int j=1;j<=i;++j) {
    for (int k=1;k<j;++k) f[i][j][1] += f[i-1][k][0];for (int k=j;k<i;++k) f[i][j][0] += f[i-1][k][1];}return;
}void work(void)
{
    cin>>n>>m;int last, k;bool used[N] = {
    };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];} printf("%d", last);used[last] = 1;for (int i=2;i<=n;++i){
    k ^= 1;int j = 0;for (int len=1;len<=n;++len){
    if (used[len]) continue;j ++;if (k == 0 && len < last || k == 1 && len > last) {
    if (f[n-i+1][j][k] >= m) {
    last = len;break;}else m -= f[n-i+1][j][k];}}used[last] = 1;printf(" %d", last);}puts("");
}signed main(void)
{
    freopen("fence.in","r",stdin);freopen("fence.out","w",stdout);DP();int T; cin>>T;while (T --) work();return 0;
}