题解：P14568 【MX-S12-T3】排列

妈妈我能场切 T3 了。

考虑一个排列是如何生成的，一个很经典的想法是，认为一开始有一个空序列，我们依次向里面插入

1, 2, 3, \ldots, n

，那么会得到一个排名序列，其反排列就是我们要的排列。

如果没有看懂，可以先去看看 P3757 和 P4099。

这么做的好处是，我们不再需要关注一个位置的具体值，反而将重心放到了排名上去，而这正是我们真正需要的。

那么我们先排除掉无解的情形，就是说有一个

2

在

0

左边，或者有一个

3

在

1

左边。

那么对于

op_i \in \{0, 1\}

，将这个数扔在最左 / 右的位置，否则就是在强制要求接下来的数字必须扔在自己的左 / 右的位置，发现这个数字的插入方法数与前面的序列给这个数字留了几个能插入的位置有关。

考虑 DP，设

f_{i, j}

为已经填了

i

个位置，且填完之后给后面留了

j

个位置，那么：

对于 $op_i \in \{0, 1\}$ 的，我们填完这个数后会多出一个位置，即 $f_{i, j} \leftarrow f_{i - 1, j - 1}$ ；
否则我们可以将这个数填在任意一个之前留给我们的位置中，填完之后留下来的位置个数一定不会变多，且可能取到不多于填前的任意一个数，即 $f_{i, j} \leftarrow \sum_{k \ge j} f_{i - 1, k}$ 。

初始状态分

op_1

是否比

1

小，如果比

1

小那么会留下两个空位，否则只有一个。

直接做是

O(n ^ 3)

的，显然第二种转移可以后缀和优化成

O(n ^ 2)

的，那么转移就成了：

对于 $op_i \in \{0, 1\}$ 的，将 $f$ 数组向后平移一位；
否则对 $f$ 数组原地做一遍后缀和。

代码如下，非常简单：

CPP

namespace LCL {
    constexpr int MAXN = 5e3 + 10, MAXV = MAXN << 2;
    int n, a[MAXN], f[MAXN];
    bool chk() { // 2, ..., 0  3, ..., 1
        bool p2 = 0, p3 = 0;
        rep(i, 1, n) switch (a[i]) {
            case 0:
                if (p2) return 0;
                break;
            case 1:
                if (p3) return 0;
                break;
            case 2:
                p2 = 1;
                break;
            case 3:
                p3 = 1;
                break;
        }
        return 1;
    }
    void main() {
        cin >> n;
        rep(i, 1, n) cin >> a[i];
        if (!chk()) cout << 0, exit(0);
        if (a[1] > 1)
            f[1] = 1;
        else
            f[2] = 1;
        rep(i, 2, n) {
            if (a[i] <= 1) {
                per(i, n + 1, 1) f[i] = f[i - 1];
                continue;
            }
            per(i, n + 1, 1) add(f[i], f[i + 1]);
        }
        per(i, n + 1, 1) add(f[i], f[i + 1]);
        cout << f[1];
    }
} // namespace LCL

题解：P14568 【MX-S12-T3】排列

文章操作

相关推荐

评论

题解：P14568 【MX-S12-T3】排列