「BZOJ 3591」最长上升子序列

题目大意：

在 $n \log n$ 求最长上升子序列的算法中用到的 $d$ 数组上进行三进制压位，$0$ 表示该数字还未访问到，$1$ 表示该数字访问到了且仍在 $d$ 数组中，$2$ 表示访问过来且已被弹出 $d$ 数组。

由于每次转移是 $0$ 变成 $1$，$1$ 变成 $2$，因此从小到大枚举状态即可。

#include <cstdio>

const int N = 14348910;
int f[N] = {1}, p[20] = {1}, a[20], b[20], n, m, ans;

bool check(int x) { //有m个1, n-m个2
    int i = 0, j = 0;
    while (x) i += (x % 3 == 1), j += (x % 3 == 2), x /= 3;
    if (i == m && j == n - m) return true; return false;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i)
        scanf("%d", &a[i]), b[a[i]] = i;
    for (int i = 1; i <= n; ++i) p[i] = p[i-1] * 3;
    for (int x = 0; x < p[n]; ++x) { //枚举当前状态
        int t = x, s = 0;
        while (t) s += (t % 3 == 1), t /= 3;
        if (s > m) continue;
        if (check(x)) ans += f[x];
        for (int j = 1; j <= n; ++j) { //枚举新添的元素
            if (x / p[j-1] % 3) continue; //判断是否已经访问过了
            if (b[j] > 1 && !(x / p[a[b[j]-1]-1] % 3)) continue; //判断LIS中上一个元素是否已经访问过
            int y = x + p[j-1];
            for (int k = j + 1; k <= n; ++k) //寻找被替换的元素
                if (x / p[k-1] % 3 == 1) { y += p[k-1]; break; }
            f[y] += f[x];
        }
    }
    printf("%d\n", ans);
    return 0;
}

时间复杂度 $O(3^nn^2)$