【ACwing 1064 小国王】状压dp

题目链接

题意

你需要在一个n*n的棋盘放k个棋子，使得他们互不攻击，每个国王都会对其相邻的8个位置攻击，现在问你有多少个放置方案

思路

数据量是10，很明显的状压dp题，f[i][j][k]代表的是已经摆好了前i-1行，现在第i行状态为j，一共的棋子数是k的方案数，每一种合法状态我们可以提前预处理出来，还有每种状态能转移的状态也可以预处理出来，然后就是状压dp的部分，有一个地方需要注意，就是状态转移预处理的时候要判断左移和右移的情况，本来我写的只有左移，发现答案比标准答案大，就是预处理的时候能转移的状态增加了，所以又加了一个右移的判断之后就正确了，下面请看代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 12;
vector<long long> hefa;
vector<long long> zhuanyi[1<<N];
long long f[N][1<<N][N*N],cnt[1<<N];
int count(int x){
    
	int ans = 0;
	while(x) ans += (x&1),x >>= 1;
	return ans;
}
int main(){
    
	int n,k;	
	cin>>n>>k;
	zhuanyi[0].push_back(0);
	for(int i=0;i<(1<<n);i++){
    
		if((i&(i>>1)) == 0) hefa.push_back(i);
		cnt[i] = count(i);
	}
	f[0][0][0] = 1;
	for(int i=0;i<hefa.size();i++){
    
		for(int j=i+1;j<hefa.size();j++){
    
			long long x = hefa[i],y = hefa[j];
			if(((x>>1)&(y)) == 0 && (x&y) == 0 && (x&(y>>1)) == 0) zhuanyi[x].push_back(y),zhuanyi[y].push_back(x);
			//就这个地方，要同时判断(x>>1)&(y) == 0和(x&(y>>1)) == 0，不然会出错
		}
	}
// for(int i=0;i<hefa.size();i++){
    
// cout<<hefa[i]<<' ';
// for(auto t : zhuanyi[hefa[i]]) cout<<t<<' ';
// cout<<endl;
// }
	long long ans = 0;
	for(int i=1;i<=n;i++){
    
		for(int s=0;s<=k;s++)
			for(auto x : hefa){
    
				for(auto y : zhuanyi[x]){
    
					if(s >= cnt[x])
					f[i][x][s] += f[i-1][y][s-cnt[x]];
				}
			}
	}
	for(auto t : hefa) ans += f[n][t][k];
	cout<<ans<<endl;
	return 0;
}