conniesarah
大国重器2008
2021-01-21 22:57

洛谷互不侵犯(c++小白求助)

  • c++

这哪里错了

#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复制

16

报错信息

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享

3条回答