bzoj1087/scoi2005 互不侵犯

题目描述

在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;
}