Date：2022.04.08
题意描述：
在 n×n 的棋盘上放 k 个国王，国王可攻击相邻的 8 个格子，求使它们无法互相攻击的方案总数。
输入格式
共一行，包含两个整数 n 和 k。
输出格式
共一行，表示方案总数，若不能够放置则输出0。
数据范围
1≤n≤10,
0≤k≤n2
输入样例：
3 2
输出样例：
16
思路：
f
[
i
]
[
j
]
[
k
]
:
f[i][j][k]:
f[i][j][k]:已经在前
i
i
i行摆完
k
k
k个国王，其中第
i
i
i行摆放方式固定为
j
j
j的合法摆放方案数。
c
o
u
n
t
(
i
)
:
count(i):
count(i):状态
i
i
i中1的个数。
我们最后一个状态是
j
j
j，因此我们讨论所有满足条件的
f
[
i
?
1
]
[
x
]
[
j
?
c
o
u
n
t
(
j
)
]
f[i-1][x][j-count(j)]
f[i?1][x][j?count(j)]，其中前一行摆放状态
x
x
x不能与当前行摆放状态
j
j
j冲突。
①
x
&
j
=
=
0
x\&j==0
x&j==0：即相邻两行没有任何一列两个状态都是1。
②
x
∣
j
x|j
x∣j这一状态不存在连续两个相邻的1。
因此我们可以枚举两行的所有状态，预处理出所有合法的状态。
起始：
f
[
0
]
[
0
]
[
0
]
=
1
;
f[0][0][0]=1;
f[0][0][0]=1;【前0行已经放了0个国王，第0行状态是0（也就是一个没放）的方案数】
终止：
f
[
n
+
1
]
[
0
]
[
k
]
;
f[n+1][0][k];
f[n+1][0][k];
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int N = 12,M=1<<N,K=110;
typedef long long LL;
LL n,m,k,t,f[N][M][K],cnt[M];
LL lowbit(LL x) {return x&-x;}
vector<LL>state[M];
bool check(LL state)
{
for(int i=0;i<n-1;i++)
if((state>>i)&1 && (state>>(i+1)&1)) return false;
return true;
}
LL count(LL state)
{
LL res=0;
while(state) {state-=lowbit(state);res++;}
return res;
}
int main()
{
cin>>n>>k;
for(int i=0;i<(1<<n);i++) cnt[i]=count(i);
for(int i=0;i<(1<<n);i++)
for(int j=0;j<(1<<n);j++)
if(check(i|j)&&(i&j)==0) state[i].push_back(j);
f[0][0][0]=1;
for(int i=1;i<=n+1;i++)
for(int a=0;a<(1<<n);a++)
for(int b=0;b<state[a].size();b++)
for(int t=0;t<=k;t++)
if(t>=cnt[a])
f[i][a][t]+=f[i-1][state[a][b]][t-cnt[a]];
cout<<f[n+1][0][k];
return 0;
}
还能有个小优化，我们又发现每一行都必须合法，因为即使同一行放国王也可能彼此攻击到，因此每一行合法的前提也是“不能有连续两个相邻的1”。因此我们预处理出每一行都合法的状态，枚举每一行的状态时枚举它就好，会快一点点。
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int N = 12,M=1<<N,K=N*N;
typedef long long LL;
LL n,m,k,f[N][K][M],cnt[M];
vector<LL>state,hefa[M];
LL lowbit(LL x) {return x&-x;}
bool check(LL a)
{
for(int i=0;i<n-1;i++)
if(a>>i&1 && a>>(i+1)&1) return false;
return true;
}
LL count(LL state)
{
LL res=0;
while(state) {state-=lowbit(state);res++;}
return res;
}
int main()
{
cin>>n>>k;
for(int i=0;i<(1<<n);i++)
if(check(i))
{state.push_back(i);cnt[i]=count(i);}
for(int i=0;i<state.size();i++)
for(int j=0;j<state.size();j++)
if(check(state[i]|state[j])&&(state[i]&state[j])==0)
hefa[state[i]].push_back(state[j]);
f[0][0][0]=1;
for(int i=1;i<=n+1;i++)
for(int j=0;j<=k;j++)
for(int a=0;a<state.size();a++)
for(int b=0;b<hefa[state[a]].size();b++)
{
LL c=cnt[state[a]];
if(j>=c)
f[i][j][state[a]]+=f[i-1][j-cnt[state[a]]][hefa[state[a]][b]];
}
cout<<f[n+1][k][0];
return 0;
}
