P1896互不侵犯

传送门
很显然暴搜不能通过，容易想到使用状压 DP，设 \(f_{i,p,j}\) 表示第 \(i\) 行状态为 \(j\) 总共放了 \(p\) 个国王的可行方案数。转移较为显然，枚举上一行的状态 \(o\)，预处理对于每个状态的国王数数组 \(num_{sta}\)，则有转移方程 \(f_{i,p,j} += f_{i-1,p-num_{j},o}\)，初始状态 \(f_{0,0,0} = 1\)，注意判断状态 \(j\) 的合法性以及状态 \(j\) 与 \(o\) 之间是否存在八连通，通过位运算实现。答案即为最后一行所有可行状态总共 \(k\) 个国王的方案数之和，即 \(\sum_{valid_{sta}=true} f_{n,k,sta}\)。

#include
#define int long long
using namespace std;
int n,k,ans;
int num[1024];
int f[10][90][1024];
void cal(int x)
{
	int tmp = x;
	while(tmp)
	{
		num[x] += (tmp & 1);
		tmp >>= 1;
	}
}
bool check(int status)
{
	if((status & (status >> 1)) or (status & (status << 1))) return false;
	else return true;
}
signed main()
{
	scanf("%lld%lld",&n,&k);
	for(int i = 0;i < (1 << n);i++)
	    cal(i);
	f[0][0][0] = 1;
	for(int i = 1;i <= n;i++)
	{
		for(int j = 0;j < (1 << n);j++)
		{
			if(not check(j)) continue;
			for(int o = 0;o < (1 << n);o++)
			{
				if(not check(o)) continue;
				if((j & o) or (j & (o >> 1)) or ((j << 1) & o) or (o & (j >> 1)) or (o & (j << 1))) continue;
				for(int p = k;p >= num[j] + num[o];p--)
					f[i][p][j] += f[i-1][p-num[j]][o];
			}
		}
	}
	for(int i = 0;i < (1 << n);i++) if(check(i)) ans += f[n][k][i];
	printf("%lld\n",ans);
	return 0;
}