1087: [SCOI2005]互不侵犯King

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 5528 Solved: 3237
[Submit][Status][Discuss]

Description

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

Input

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

Output

　　方案数。

Sample Input

3 2

Sample Output

刚开始看上去很像八皇后问题，爆搜？实际上写了一遍爆搜发现TLE了，仔细分析可以发现状态实在是太多了，于是开始翻题解，发现是动态规划

状压DP，以二进制压缩状态

首先给出动规方程：

[f[i][j][now]=sum _{last=0}^{(1<<n)-1}f[i-1][j-num[now]][last]]

其中最大的难点是怎么判断国王位置合法，这就要用到神奇的二进制位运算了，想起了著名的约瑟夫问题，也是利用二进制得出答案

对于当前行，设当前状态为now，!now&(now<<1)，如果成立，则当前行合法。因为这就排除了两个国王相邻的可能性

对于上下相邻的两行，用类似算法，!(now&(last<<1)) && !((now<<1)&last) && !(now&last)

是不是看的眼睛有点花，需要仔细分析

为了代码简洁，实际使用continue进行排除处理

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 
 5 #define LL long long
 6 
 7 const int MAXN=1<<9;
 8 
 9 LL n,k,ans;
10 LL num[MAXN],f[10][82][MAXN];
11 
12 void init()
13 {
14     for(int i=0;i<(1<<n);i++)
15         if(!(i&(i<<1)))
16         {
17             int t=i;
18             while(t)
19             {
20                 num[i]+=t&1;
21                 t>>=1;
22             }
23             f[1][num[i]][i]=1;
24         }
25 }
26 
27 int main()
28 {
29     cin>>n>>k;
30     init();
31     for(int i=2;i<=n;i++)
32         for(int j=0;j<=k;j++)
33             for(int now=0;now<(1<<n);now++)
34             {
35                 if((now&(now<<1))||j<num[now]) continue;
36                 for(int last=0;last<(1<<n);last++)
37                 {
38                     if(now&(last<<1)||((now<<1)&last)||(now&last)) continue;
39                     f[i][j][now]+=f[i-1][j-num[now]][last];
40                 }
41             }
42     for(int i=0;i<(1<<n);i++)
43         ans+=f[n][k][i];
44     cout<<ans;
45     return 0;
46 }