[数据结构与算法]Acwing 1064. 小国王（状压DP）

?由题意，一个国王周围的8个方格都不能放置另外的国王，我们按照逐行放置的顺序，可知在放置某位置时，其左上、上方、右方以及左右均不能存在国王，即如图1~5号方格

我们用二进制表示一行的状态

（1）对于4.5号，通过预处理筛选出相邻两位不同时是1的所有合法状态，并储存在st中

bool check(int x)
{//是否存在相邻的1 
	for(int i=0;i<n;i++)
		if((x>>i&1)&&(x>>i+1&1))
			return false;
	return true;
}
//预处理出所有合法状态 
for(int i=0;i<1<<n;i++)
	if(check(i))
	{
		st.push_back(i);
		cnt[i]=count(i); 
	}

?（2）对于1~3号，筛选出每个状态x可以转移到的所有合法状态（即一个在第i-1行，一个在i行时，互相不发生冲突），并储存到h[x]（存的是状态的下标）

可以相互转移需要满足：

????????①对应位置不同时是1（2号格），即a&b==0

????????②合起来没有相邻的1（1.3号格），即check(a|b)==true

注意：这里状态用的都是存在st中的下标

//两个合法状态可以相互转移，满足：
	//对应位置不能同时是1，合起来没有相邻的1 
	for(int i=0;i<st.size();i++)
		for(int j=0;j<st.size();j++)
		{
			int a=st[i],b=st[j];
			if((a&b)==0&&check(a|b))
				h[i].push_back(j);//注意用的都是下标 
		}

（3）状态转移?

初始状态为第0行放置0个且状态为0（st[0]=0）

枚举第i行放置j个且第i行状态为st[k]时，这个局面可以由第i-1行放置c(j>=c)个，且第i-1行状态为h[k][u]（0<u<h[k].size）转移而来

    f[0][0][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=m;j++)
			for(int k=0;k<st.size();k++)
			{
				int s=st[k];//当前状态 
				int c=cnt[s];//1的个数
				//枚举当前状态可以互相转移的状态 
				for(int u=0;u<h[k].size();u++)
					if(j>=c)
						f[i][j][k]+=f[i-1][j-c][h[k][u]];
			}
	ll res=0;
	for(int i=0;i<st.size();i++)
		res+=f[n][m][i];
	cout<<res;

（4）全部代码：?

#include<iostream>
#include<vector>
using namespace std;
const int N=12,M=1<<10,K=105;
int n,m;
typedef long long ll;
vector<int> st;//所有合法状态(不存在连续的1)
int cnt[M];//状态中1的个数 
vector<int> h[M];//每个状态可以转移到的其他状态 
ll f[N][K][M];
//f[i][j][k] 完成前i行，放了j个，第i行状态为k（k为下标，实际状态为st[k]）的方案数 
bool check(int x)
{//是否存在相邻的1 
	for(int i=0;i<n;i++)
		if((x>>i&1)&&(x>>i+1&1))
			return false;
	return true;
}
int count(int x)
{//1的个数 
	int res=0;
	for(int i=0;i<n;i++)
		res+=x>>i&1;
	return res;
}
int main()
{
	cin>>n>>m;
	//预处理出所有合法状态 
	for(int i=0;i<1<<n;i++)
		if(check(i))
		{
			st.push_back(i);
			cnt[i]=count(i); 
		}
	//两个合法状态可以相互转移，满足：
	//对应位置不能同时是1，合起来没有相邻的1 
	for(int i=0;i<st.size();i++)
		for(int j=0;j<st.size();j++)
		{
			int a=st[i],b=st[j];
			if((a&b)==0&&check(a|b))
				h[i].push_back(j);//注意用的都是下标 
		}
	f[0][0][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=m;j++)
			for(int k=0;k<st.size();k++)
			{
				int s=st[k];//当前状态 
				int c=cnt[s];//1的个数
				//枚举当前状态可以互相转移的状态 
				for(int u=0;u<h[k].size();u++)
					if(j>=c)
						f[i][j][k]+=f[i-1][j-c][h[k][u]];
			}
	ll res=0;
	for(int i=0;i<st.size();i++)
		res+=f[n][m][i];
	cout<<res;
}