骑士

题目描述：

在 n×n 的棋盘上放 k 个国王，国王可攻击相邻的 8个格子，求使它们无法互相攻击的方案总数。

输入格式

共一行，包含两个整数 n和 k。

输出格式

共一行，表示方案总数，若不能够放置则输出0。

数据范围

\(1≤n≤10,\) \(0≤k≤n^2\)

输入样例：

1
3 2

输出样例：

1
16

本题就是典型的状态压缩DP。

分为两个部分进行分析：

状态表示

f[i][j][s]表示所有只摆在前i行，已经摆了j个国王，并且第i行摆放的状态时s的所有方案的集合。

属性

Count（属于计算数量）

经过集合划分（第i排只取决于第i-1排，因此集合划分只需要考虑i-1排的\(2^n\)次方种方案即可）

已经摆完了前i排，并且第i排的状态是a，第i-1排的状态时b，已经摆了j个国王的所有方案实际上等价于->

已经摆完了前i-1排，并且第i-1排的状态时b，已经摆了j-count(a)个国王的所有方案，也就是f[i-1][j-count(a)][b]

思考清楚了转移，接下来看一下要怎么样才能从i-1行到第i行进行一个转移：

只需要满足以下式子即可：

1
2
(a&b)==0
(a|b)不能有两个相邻的1

贴上代码

解释详情看注释：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<iostream>
#include<vector>
using namespace std;
const int N=12,M=1<<10,K=110;
int n,m;
vector<int>state;
//存放所有合法状态
vector<int>head[M];
//存放所有合法状态所能到达的状态
int id[M];
int cnt[M];
//存放每个状态1的数量
int f[N][K][M];
//含义见上方
bool check(int state)//是否一个合法状态
{
    for(int i=0;i<n;i++)
    {
        if((state>>i&1)&&(state>>i+1&1))
        {
            return false;
        }
    }
    return true;
}
int count(int state)//计算1的数量
{
  int ans=0;
    for(int i=0;i<n;i++)
    {
        ans+=state>>i&1;
    }
    return ans;
}
int main()
{
cin>>n>>m;
for(int i=0;i<1<<n;i++)
if(check(i))
{
    state.push_back(i);
    id[i]=state.size()-1;
    cnt[i]=count(i);
}
 
for(int i=0;i<state.size();i++)
{
    for(int j=0;j<state.size();j++)
    {
        int a=state[i];
        int b=state[j];
        if((a&b)==0&&check(a|b))
        {
            head[i].push_back(j);
        }
    }
}
f[0][0][0]=1;
    //状态转移
for(int i=1;i<=n+1;i++)
    for(int j=0;j<=m;j++)
        for(int a=0;a<state.size();a++)
            for(int b:head[a])
            {
               int c=cnt[state[a]];
                if(j>=c)
                {
                    f[i][j][a]+=f[i-1][j-c][b];
                }
			}
    cout<<f[n+1][m][0];
    return 0;
}