经常有点小迷糊 2021-01-21 22:57 采纳率: 96.7%
浏览 42
已结题

洛谷互不侵犯(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条回答 默认 最新

  • 蒟蒻一枚 2021-01-22 08:39
    关注

    这样就能100啦~

    #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 y) {
        int res = 0, x = y;
        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);
                if (king[i] <= k) {     // 这个加了一个=
                	f[1][cnt][king[cnt]] = 1;
                }
            }
        }
    }
    void dp() {
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= cnt; j++) { //当前行选定的状态
                int st = s[j];
                for (int l = 1; l <= cnt; l++) { //上一行的有效状态
                    int so = s[l];
                    if ((st & so) || (st & (so << 1) || ((st << 1) & so))) {
                        continue;	
                    }
                    for (int c = 1; c <= k; c++) {
                    	if (king[j] + c > k) {       // 这里加了一个判断
                    		continue;
    					}
                        f[i][j][c + king[j]] += f[i - 1][l][c];
                    }
                }
            }
        }
        long long ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= cnt; ++j) {
            	ans += f[i][j][k];
    		}
        }
        printf("%lld", ans);
    }
    int main() {
        pre();
        dp();
        return 0;
    }
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(2条)

报告相同问题?

问题事件

  • 系统已结题 8月10日
  • 已采纳回答 8月2日

悬赏问题

  • ¥100 有人会搭建GPT-J-6B框架吗?有偿
  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名