【状压dp】bzoj1087 || scoi2005互不侵犯

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

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

方案数。

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
long n, k, m;
long state[600][2];
long long f[20][100][600];
long cala(long x)
{
	long sum = 0;
	while (x > 0)
	{
		if ((x & 1) == 1) sum++;
		x >>= 1;
	}
	return sum;
}
int main()
{
	//freopen("king.in", "r", stdin);
	scanf("%d%d", &n, &k);
	m = 0;
	long r = ((1 << n) - 1);

	for (long i = 0; i <= r; i++)
	{
		if ((i & (i >> 1)) == 0)
		{
	        long tmp = cala(i);
			if (tmp <= k)
			{
				m++;
				state[m][0] = i;
				state[m][1] = tmp;
			}
		}
	}
	memset(f, 0, sizeof(f));
 	for (long i = 1; i <= m; i++)
	{
		f[1][state[i][1]][i] = 1;
	}
	for (long i = 2; i <= n; i++)
	{
	    for (long j = 0; j <= k; j++)
	    {
			for (long p = 1 ; p <= m; p++)
			for (long q = 1 ; q <= m; q++)
			{
			    if ((state[p][0] & state[q][0]) != 0) continue;
			    if ((state[p][0] & (state[q][0] << 1)) != 0) continue;
			    if ((state[p][0] & (state[q][0] >> 1))  != 0) continue;
				if ((j - state[q][1]) >= 0)
				{
					f[i][j][q] += f[i - 1][j - state[q][1]][p];
					//cout << i<<' ' <<j <<' '<<q <<' '<< f[i][j][q]<< endl;
				}
			}
	    }
	}
	long long re = 0;
	for (long i = 0; i <= m; i++)
	{
		re += f[n][k][i];
	}
	cout << re << endl;
    return 0;
}