题面

题目传送门

在 $N*N$ 的棋盘上放 $K$ 个国王，国王可攻击相邻的 $8$ 个格子，求使它们无法互相攻击的方案总数。

思路

状压 DP 的模板，以前 DP 技能一直没怎么点，现在数据结构什么的都差不多了，开始补 DP。

预处理

对于每一行来说，我们可以用二进制来表示当前这一行的放置状态。然后再压成十进制。

然后预处理出对于一行来说的所有状态（dfs）。

用 $s[i]$ 表示对于一行的第 i 种状态， $t[i]$ 表示这种状态用掉多少个棋子。

用 $f[i][j][k]$ 表示第 i 行，状态为 j，总共（包括之前）用了 k 个棋子的方法数。

然后用位运算来判断前后两行是否合法，转移就好了。

代码

#include<bits/stdc++.h>
using namespace std;
long long n,K,cnt=0,s[100000],t[100000],f[20][200][200],ans=0;
void dfs(int now,int sum,int pos){
	if (pos>=n){
		s[++cnt]=now;
		t[cnt]=sum;
		return;
	}
	dfs(now,sum,pos+1);
	dfs(now+(1<<pos),sum+1,pos+2);
}
int main(){
	cin>>n>>K;
	dfs(0,0,0);
	for (int i=1;i<=cnt;i++){
		f[1][i][t[i]]=1;
	}
	for (int i=2;i<=n;i++){
		for (int j=1;j<=cnt;j++){
			for (int k=1;k<=cnt;k++){
				if ((s[j]&s[k])||((s[j]<<1)&s[k])||((s[j]>>1)&s[k])){
					continue;
				}
				for (int x=K;x>=t[j];x--){
					f[i][j][x]+=f[i-1][k][x-t[j]];
				}
			}
		}
	}
	for (int i=1;i<=cnt;i++){
		ans+=f[n][i][K];
	}
	cout<<ans;
}