1. 题目大意

在 N×NN \times N 的棋盘里面放 KK 个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 88 个格子。

注意是8个方向。

对于全部数据，1≤N≤91 \le N \le 9，0≤K≤N×N0 \le K \le N\times N。

从这个数据范围看出是状压动规，暴搜明显超时。

2. 思路分析

现在知道是状压动规，考虑如何建立状态、转移方程、边界。

  • 状态

    首先，1≤N≤91 \le N \le 9，可以想到用一个长 99 位的二进制串来表示状态。

    思考一下转移必须的条件，可以把每一行作为一个阶段（于是有了第一维），还需要知道这一行的选取情况（第二维），此外，还要知道已经用掉的国王数量（第三维）。

    于是有了具体的状态定义：令 dp[i][j][k] 表示第 ii 行，使用 jj 的方法安放，已经用了 kk 个国王。

    为了方便后续的判断，也节省时间，可以把一行中所有合法的状态全部处理出来，存入数组中。

  • 转移方程

    明显，要从第 i−1i-1 个状态转移过来。

    枚举所有的当前状态和上一个状态，再枚举已经用去的国王数，把符合条件的累加起来。得到转移方程：

    dpi,now,k=∑dpi−1,lst,k−v(v是now状态所用去的国王数量)dp_{i,now,k}=\sum dp_{i-1,lst,k-v}\\ \\ (v是now状态所用去的国王数量)

    基本完成，还有一个小问题——怎么判断两行状态是否合法？

    • 上下

      很好处理，把两个状态取 &\& ，如果答案不等于0，说明不可行。如图：

    • 对角

      考虑把一个状态左移一个，就转化为了上下的情况。如图：

    于是有了上下和对角的判断函数：

    1
    2
    3
    4
    5
    6
    //x,y是相邻两行的状态
    bool check(int x,int y){
        if((x&y)||((x<<1)&y)||(x&(y<<1)))
            return false;
        return true;
    }

    • 左右

      上面提到可以通过预处理确定一行中左右的合法情况，这里具体说明：直接用 dfs 预处理可以的情况，写法如下：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
            //d表示当前处理的列号，tot表示使用的国王总数，val表示建立起的状态二进制串
      void init(int d,int tot,int val){
          if(d>n){
              num++;
              a[num]=val;
              v[num]=tot;
              return;
          }
          init(d+1,tot,val);
                //这一格空着
          init(d+2,tot+1,val|(1<<(d-1)));
                //这一格填上，直接通过+2跳过下一个，避免相邻
      }

  • 边界

    明显，第一行所有状态都是 11。

  • 答案

    易得：

    ans=∑dpn,i,k(i遍历所有状态) ans=\sum dp_{n,i,k} \\ (i遍历所有状态)

3. 注意事项

  1. 会爆 int，要开long long！
  2. 注意位运算优先级，保险起见加上括号！

4. code

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
#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[2000],num;
int v[2000];
long long dp[20][2000][200];
void init(int d,int tot,int val){
    if(d>n){
        num++;
        a[num]=val;
        v[num]=tot;
        return;
    }
    init(d+1,tot,val);
    init(d+2,tot+1,val|(1<<(d-1)));
}
bool check(int x,int y){
    if((x&y)||((x<<1)&y)||(x&(y<<1)))
        return false;
    return true;
}
int main(){
    cin>>n>>k;
    init(1,0,0);
    for(int i=1;i<=num;i++)
        dp[1][i][v[i]]=1;
    for(int i=2;i<=n;i++)
        for(int now=1;now<=num;now++)
            for(int lst=1;lst<=num;lst++)
                if(check(a[lst],a[now]))
                    for(int sum=v[now];sum<=k;sum++)
                        dp[i][now][sum]+=dp[i-1][lst][sum-v[now]];
    long long ans=0;
    for(int i=0;i<=num;i++)
        ans+=dp[n][i][k];
    cout<<ans<<endl;
    return 0;
}