这哪里错了

#include <cstdio>
using namespace std;
int n, k, cnt;
int s[1000], king[1000]; //一行内的合法状态
long long f[10][1000][100]; //[i][j][k] 在第i行状态为j共有k个国王时的摆法数量

int getkings(int x) {
    int res = 0;
    while (x) {
        res += (x & 1);
        x >>= 1;
    }
    return res;
}
int pre() {
    scanf("%d%d", &n, &k);
    int maxn = (1 << n);
    for (int i = 0; i < maxn; i++) {
        if (!(i & (i << 1))) {
            s[cnt] = i;
            king[cnt] = getkings(i);
            f[1][cnt][king[cnt]] = 1;
        }
    }
}
void dp() {
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= cnt; j++) { //当前行选定的状态
            int st = s[j];
            for (int l = 0; l <= cnt; l++) { //上一行的有效状态
                int so = s[l];
                if ((st & so) || (st & (so << 1) || (st & (so >> 1)))) {
                    continue;
                }
                for (int c = 0; c <= k; c++) {
                    f[i][j][c + king[j]] += f[i - 1][1][c];
                }
            }
        }
    }
    long long ans = 0;
    for (int i = 0; i < cnt; i++) {
        ans += f[n][i][k];
    }
    printf("%lld", ans);
}
int main() {
    pre();
    dp();
    return 0;
}

展开

题目描述

在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。

注：数据有加强（2018/4/25）

输入格式

只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）

输出格式

所得的方案数

输入输出样例

输入 #1复制

3 2

输出 #1复制

报错信息

电话号码格式：09开头的11位数号码的正则表达式

qq_39464862

2个回复