[BZOJ1087] [SCOI2005] 互不侵犯King (状压dp)

Description

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

Input

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

Output

　　方案数。

Sample Input

3 2

Sample Output

HINT

Source

Solution

　　状压$dp$就是把状态压缩成二进制数，利用二进制的位运算改进算法的一种方法

　　这道题就把单行每个格子是否放国王当成状态，这样每一行就是一个不超过$2^n$的数，然后就可以光明正大地用按位与运算判断是否攻击

　　可以预处理单行所有合法状态，就不用每个二进制数枚举了。实际验证其合法方案数就是$Fibonacci_{n+2}$，比$2^n$小很多

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 ll f[][][], cnt[], a[];

 bool check(int j, int k)

 {

     if(j & k <<  || j & k || j & k >> ) return false;

     return true;

 }

 int main()

 {

     int n, m, tot = ;

     ll (*f0)[] = f[], (*f1)[] = f[], ans = ;

     cin >> n >> m;

     f1[][] = ;

     for(int i = ; i <  << n; ++i)

     {

         for(int j = ; j < ; ++j)

             if(i &  << j) ++cnt[i];

         if(!(i & i << ) && !(i & i >> ))

             a[++tot] = i;

     }

     for(int i = ; i <= n; ++i)

     {

         swap(f0, f1);

         memset(f1, , );

         for(int j = ; j <= tot; ++j)

             for(int k = ; k <= tot; ++k)

                 for(int l = cnt[a[j]]; l <= (i - ) * n; ++l)

                     if(check(a[j], a[k]))

                         f1[l + cnt[a[k]]][a[k]] += f0[l][a[j]];

     }

     for(int i = ; i <= tot; ++i)

         ans += f1[m][a[i]];

     cout << ans << endl;

     return ;

 }

秒客网