动态规划
判断方案的合法性
因为枚举i-1层的状态和第i层的状态所需的循环过多导致时间复杂度很高,所以在这里我们运用预处理的方式来解决此题,用
st数组来存储不存在连续个1的合法方案数,用head数组来存储与合法方案数进行’|’和’&’运算后的合法方案数
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=12;
long long f[N][1<<N][110];
int sum[1<<N];//表示1的数量
vector<int> line;//存储第i行的合法状态
vector<int> row[1<<N];//row[i]表示第i行的上一行的合法方案
int main()
{
int n,m;
cin>>n>>m;
for(int i=0;i<1<<n;i++)//先预处理出与本行不冲突的,即不能有相邻的1
{
int cnt=0,num=0;
bool flag=true;
for(int j=0;j<n;j++)
if(i>>j&1)
{
num++;
if(cnt==1)
{
flag=false;
break;
}
cnt=1;
}
else cnt=0;
if(flag)
{
line.push_back(i);
sum[i]=num;
}
}
for(auto i:line)//预处理与上行不冲突的数组
for(auto j:line)
{
bool flag=true;
if(i&j||!count(line.begin(),line.end(),i|j)) flag=false;
if(flag) row[i].push_back(j);
}
f[0][0][0]=1;
for(int i=1;i<=n+1;i++)//枚举行数
for(auto t:line)//枚举当前行数的状态
for(int k=0;k<=m;k++)//枚举当前已经放了几个国王
for(auto q:row[t])//枚举上一行的状态
{
if(sum[t]>k) break;
if(sum[t]+sum[q]>k) continue;
f[i][t][k]+=f[i-1][q][k-sum[t]];
}
cout<<f[n+1][0][m]<<endl;
return 0;
}