AcWing 309. 装饰围栏

题目链接

这道题与下一章的数位\(dp\)解题思路十分一致。

把寻找答案变成按位（并且是字典序从小到大）枚举当前这一位可以填的情况。
通过\(dp\)预处理的信息告诉我们可行性，就可以把答案紧逼到一个更小的（子）问题，非常有趣。

考虑 \(dp\) 预处理的信息：

\(f[i][j][0 / 1]\) 表示 \(i\) 块木板，最左边的长度是第 \(j\) 小（排名为 \(j\) ），最左边这块是低位 / 高位的方案数。

由于木板的数量进行了变化，在加入一块新的木板后，木板的值域从 \([1, i - 1]\) 变成了 \([1, i]\)，所以我们可以考虑把木板的长度变为一个相对的数量，从而进行转化。

考虑第一种转移

\(f[i][j][0] = \sum_{k = j}^{i - 1}f[i - 1][k][1]\)

可以看做是把后面 \(i - 1\) 块木板中真实长度 \(>= j\) 的再抬高一格，这样再拼一个 \(j\) 的木板就是一个合适的状态。

第二种转移也类似：

\(f[i][j][1] = \sum_{k = 1}^{j - 1} f[i - 1][k][0]\)

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 21;
typedef long long LL;
int n;
bool st[N];
LL C, f[N][N][2];
void init() {
    f[1][1][0] = f[1][1][1] = 1;
    for (int i = 2; i < N; 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() {
    init();
    int T; scanf("%d", &T);
    while (T--) {
        memset(st, false, sizeof st);
        scanf("%d%lld", &n, &C);
        int k, last;
        for (int i = 1; i <= n; i++) {
            if (f[n][i][1] >= C) { k = 1, st[last = i] = true; printf("%d ", i); break; }
            else C -= f[n][i][1];
            if (f[n][i][0] >= C) { k = 0, st[last = i] = true; printf("%d ", i); break; }
            else C -= f[n][i][0];
        }
        for (int i = n - 1; i; i--) {
            k = k ^ 1;
            int d = 0;
            for (int j = 1; j <= n; j++) {
                if (st[j]) continue;
                ++d;
                if ((k == 0 && j < last) || (k == 1 && j > last)) {
                    // 要满足 j < last
                    if (f[i][d][k] >= C) { st[last = j] = true; printf("%d ", j); break; }
                    else C -= f[i][d][k];
                }
            }
        }
        puts("");
    }
    return 0;
}

AcWing 309. 装饰围栏

原文：https://www.cnblogs.com/dmoransky/p/12257602.html