y总视频里用vector保存了所有合法状态, 枚举状态少了很多. 这里采用类似阿德里安的梦想那道题的预处理方式, st数组记录某个状态是否合法, mv[i][j]记录状态i能否转移到状态j, 后面状态计算的时候还是枚举所有状态, 用这两个数组来判断是否合法就ok.

思路上比较易懂一些hh

#include <iostream>
using namespace std;

typedef long long LL;
const int N = 12, M = 1 << 10, K = 110;

int n, m;
LL f[N][K][M];
bool st[M], mv[M][M];
int cnt[M];

bool check(int state) {
    for (int i = 0; i < n; i++)
        if ((state >> i & 1) && (state >> i + 1 & 1)) return false;
    return true;
}

int count(int state) {
    int res = 0;
    for (int i = 0; i < n; i++) res += (state >> i & 1);
    return res;
}

int main() {
    cin >> n >> m;

    for (int i = 0; i < 1 << n; i++) {
        if (check(i)) st[i] = true;
        if (st[i]) {
            cnt[i] = count(i);
            for (int j = 0; j < 1 << n; j++) {
                if (check(j) && (i & j) == 0 && check(i | j))
                    mv[i][j] = mv[j][i] = true;
            }
        }
    }

    f[0][0][0] = 1;
    for (int i = 1; i <= n + 1; i++)
        for (int j = 0; j <= m; j++)
            for (int k = 0; k < 1 << n; k++) {
                if (st[k]) {
                    for (int s = 0; s < 1 << n; s++) {
                        if (st[s] && mv[s][k] && j - cnt[k] >= cnt[s])
                            f[i][j][k] += f[i - 1][j - cnt[k]][s];
                    }
                }
            }

    cout << f[n + 1][m][0] << endl;
    return 0;
}