国王

https://loj.ac/problem/10170

题目描述

  在(n imes n)的棋盘上放(k)个国王，国王可攻击相邻的(8)个格子，求使它们无法互相攻击的方案总数。

思路

  这道题的(n)比较小，我们考虑直接把棋盘的一行压成一个数，那么如果这个位置放了棋子，这个数的二进制下的数为(1)，否则为(0),我们可以先预处理处所有满足条件的行的数，在(dp)列，用(f[i][S][k])表示第(i)行状态为(S)，到目前位置共放(k)个棋子的方案数，那么(S)可以从不互相攻击的状态转移过来，直接(dp)即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int s[600],p[600];
ll f[11][500][110];
int main()
{
	int n,k,cnt=0;
	scanf("%d%d",&n,&k);
	for(int i=0;i<(1<<n);i++)
	{
		if(i&(i<<1))continue ;
		int sum=0;
		for(int j=0;j<n;j++)
			if(i&(1<<j))sum++;
		p[++cnt]=i;
		s[cnt]=sum;
	}
	f[0][1][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=cnt;j++)
			for(int l=s[j];l<=k;l++)
			{
				for(int r=1;r<=cnt;r++)
					if(!(p[j]&p[r])&&!(p[j]&(p[r]<<1))&&!(p[j]&(p[r]>>1)))
						f[i][j][l]+=f[i-1][r][l-s[j]];
			}
	long long ans=0;
	for(int i=1;i<=cnt;i++)
		ans+=f[n][i][k];
	printf("%lld
",ans);
}