一、题目

Description

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

Input

只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）

Output

方案数

Sample Input

3 2

Sample Output

16

原题链接→_→

二、题目分析

其实我们可以用一张美妙的表来解决这道题（划掉）这道题我们首先考虑暴搜解决，然而似乎状态略多会炸……

搜索不行，我们很容易能想到DP，这里我们引入一个神奇的DP——状态压缩型动态规划。状态压缩是状压DP的核心（废话！），本人在上一篇blog中详细介绍了状态压缩的思想，诸位看官不妨移步一看，可能会对理解状压DP起到一定帮助（链接→_→）

对于每一行的状态，我们用1表示国王，0表示不放国王。由于每个位置只有0和1两种状态，我们可以使用位运算判断每行的状态是否合法。例如：10101010就是一种合法状态，而11111111就不合法。每行状态表示的十进制数就是我们压缩后的状态。

我们需要做两个预处理，先枚举每行所有可能的状态，记录下合法状态。然后判断两个状态是否能作为临行放置，并用布尔类型的二维数组存储其关系。

预处理之后，就是常规的DP，状态转移方程如下：

f[i][j][now]=∑f[i-1][j-num[now]][q]

略作说明：f[i][j][k]代表前i行，总共放j个国王，第i行状态为k时的方案数。状态转移方程中的num[now]代表状态为now的行中国王的数目，q表示第i-1行的状态。

三、代码实现

1 #include
      
        2 int n,k; 3 long long ans; 4 bool s[600],map[600][600];//判断状态是否合法；判断两个状态是否能作为临行  5 int num[600];//num[i]代表编号为i的状态含有的国王数  6 long long f[10][100][600]; 7 int sum; 8 void pre_s()//预处理s数组  9 {10     int i; 11     for(i=0;i
       
        >=1;21             }22             num[i]=cnt;23             f[1][cnt][i]=1;24         }25     }26 }27 void pre_map()//预处理map数组 28 {29     int i,j;30     for(i=0;i
        
         >1)&j)))map[i][j]=true;37         }38     }39 }40 void dp()41 {42     int i,j,now;43     for(i=2;i<=n;++i)44         for(j=0;j<=k;++j)45             for(now=0;now
         
          j)continue;49                 int q;50                 for(q=0;q
          
           j)continue;55                     f[i][j][now]+=f[i-1][j-num[now]][q];56                 }57             }58 }59 int main()60 {61     scanf("%d%d",&n,&k);62     sum=1<
          
         
        
       
      

弱弱地说一句，本蒟蒻码字也不容易，转载请注明出处