商业网站设计制作公司/2345网址中国最好

题目描述

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

输入格式

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

输出格式

所得的方案数

输入输出样例

输入 #1

3 2

输出 #1

16

分析

分析就不分析了吧，这题简直就是炮兵阵地的弱化版套上个背包啊。我直接贴代码吧。

代码如下

#include <bits/stdc++.h>
#define N 10
#define LL long long
using namespace std;
int sta[105], ret, cnt[105];
LL f[N][105][105], ans;
int w(int x){int s = 0;while(x){s++;x -= x&-x;}return s;
}
int main(){int i, j, t, n, m, k, z, a, b;scanf("%d%d", &n, &k);for(i = 0; i < (1 << n); i++){if(!(i & (i >> 1))){sta[++ret] = i;cnt[ret] = w(i);}}f[0][1][0] = 1;for(i = 1; i <= n; i++){for(j = 1; j <= ret; j++){if(cnt[j] > k) break;a = sta[j];for(t = 1; t <= ret; t++){b = sta[t];if(!(a & b) && !(a & (b << 1)) && !(a & (b >> 1))){for(z = k; z >= cnt[t]; z--){f[i][t][z] += f[i-1][j][z - cnt[t]];}}}}}for(i = 1; i <= ret; i++) ans += f[n][i][k];printf("%lld", ans);return 0;
}