洛谷P1896题解

此题正解dp，具体方案请见代码注释。

!!警告:此题解拥有大量位运算，需要加括号!!

#include<iostream>
#include<vector>
#define NM 11//存储N的最大值
#define KM 1<<10//存储最多可以摆放多少个皇后
#define KIM 13//存储二进制方案转十进制最大的数
using namespace std;
int n,k;
vector <int> sta;//存储一行中可行的方案
int hmq[KM],id[KM];//hmq:存储下标方案有多少个皇后,id:存储下标方案的编号
vector <int> pairs[KM];//存储可以放在下标方案上下的编号
long long f[NM][KIM][KM];//dp数组
bool linecheck (int sta)//检查当前行是否合法
{
	return !(sta&(sta>>1));
}
int countking(int sta)//检测当前行有几个皇后
{
	int num = 0;
	for(int i = 0;i<n;++i)num+=(sta>>i)&1;
	return num;
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=0;i<(1<<n);++i)//筛选在一行中合法的方案
	{
		if(linecheck(i))
		{
			sta.push_back(i);
			id[i]=sta.size()-1;
			hmq[i]=countking(i);
		}
	}
	for(int i=0;i<sta.size();++i)//预处理哪两行可以 放在一起
	{
		for(int j=0;j<sta.size();++j)
		{
			int a=sta[i],b=sta[j];
			if((a&b)==0&&linecheck(a|b))
			{
				pairs[i].push_back(j);
			}
		}
	}
	//dp开始
	f[0][0][0]=1;
	for(int i=1;i<=n+1;i++)//循环前i行
	{
		for(int j=0;j<=k;j++)//循环前j个棋子
		{
			for(int a=0;a<sta.size();++a)//循环当前行的状态
			{
				for(int b:pairs[a])//循环上一行的状态
				{
					int c=hmq[sta[a]];
					if(j>=c)
					{
						f[i][j][a]+= f[i-1][j-c][b];//状态转移方程
					}
				}
			}
		}
	}
	printf("%lld",f[n+1][k][0]);
	return 0;
}