$\mathcal{R.T.}$

LOJ记录

代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <cstdlib>
#include <utility>
#include <queue>
#include <stack>
#include <deque>
#include <iomanip>
#include <vector>
#include <list>
#include <set>
using namespace std;
using ll = long long;
const int maxn = 11;
int N, K, cnt = 0; /*cnt记录状态总个数*/
ll f[maxn + 3][1025][maxn * maxn]; /*13.247MB*/
int stt[maxn * maxn], sta[maxn *
                          maxn]; /*stt存储每一行状态，sta[i]是stt[i]对应国王（1）的个数*/
//*预处理每一行的可行状态
void DFS(int x, int num, int bit) { /* x是状态，num是x中1 的个数，bit是从右到左第几位 */
    if (bit >= N) {
        stt[++cnt] = x;
        sta[cnt] = num;
        return;
    }

    DFS(x, num, bit + 1); /*第bit位不放1，那么考虑在bit+1位置的状态，x和num不变*/
    DFS(x + (1 << bit), num + 1, bit + 2);
}
bool cmptb(int j, int x) {
    if ((stt[j]&stt[x]) || (stt[j] & (stt[x] << 1)) || (stt[j]&stt[x] >> 1)) {
        return false;
    }

    return true;
}

int main() {
    scanf("%d%d", &N, &K);
    DFS(0, 0, 0); /*初始化每一行的状态 */

    for (int i = 1; i <= cnt; ++i) {
        f[1][i][sta[i]] = 1; //第一行选任一状态，都只有一种情况
    }

    for (int i = 2; i <= N; ++i) {
        for (int j = 1; j <= cnt; ++j) {
            for (int s = sta[j]; s <= K; ++s) {
                for (int x = 1; x <= cnt; ++x) {
                    if (!cmptb(j, x)) {
                        continue;
                    }

                    f[i][j][s] += f[i - 1][x][s - sta[j]];
                }
            }
        }
    }

    ll ans = 0;

    for (int j = 1; j <= cnt; ++j) {
        ans += f[N][j][K];
    }

    printf("%lld", ans);
    return 0;
}

希望得到大佬的帮助，谢谢。