洛谷互不侵犯（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

这样就能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;
}

最容易看出来的一个问题，就是在pre函数中，cnt一直不变，应该把s[cnt] = i; 改成 s[cnt++] = i;

把代码改成这样，调成了80分。

#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;    // 这里为了不改变i的值，不影响循环，可以用一个备份的变量
    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;    // cnt要有改动
            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++) {
                    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;
}
/*有几处for循环的初始条件，由于s[0]没有意义，所以初始值改成了1*/