这哪里错了
#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