BZOJ 1087 互不侵犯King 状态压缩DP

题目链接：

https://www.lydsy.com/JudgeOnline/problem.php?id=1087

题目大意;

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

思路：

状态压缩，预处理出每一行的合法状态，连续的两个1在一起的状态为不合法状态。

预处理出从上一行到下一行的合法情况，直接每一行推过来即可。

 #include<bits/stdc++.h>
 #define IOS ios::sync_with_stdio(false);//不可再使用scanf printf
 #define Max(a, b) ((a) > (b) ? (a) : (b))//禁用于函数，会超时
 #define Min(a, b) ((a) < (b) ? (a) : (b))
 #define Mem(a) memset(a, 0, sizeof(a))
 #define Dis(x, y, x1, y1) ((x - x1) * (x - x1) + (y - y1) * (y - y1))
 #define MID(l, r) ((l) + ((r) - (l)) / 2)
 #define lson ((o)<<1)
 #define rson ((o)<<1|1)
 #define Accepted 0
 #pragma comment(linker, "/STACK:102400000,102400000")//栈外挂
 using namespace std;
 inline int read()
 {
     int x=,f=;char ch=getchar();
     while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
     while (ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
     return x*f;
 }
 typedef long long ll;
 const int maxn =  + ;
 const int MOD = ;//const引用更快，宏定义也更快
 const int INF = 1e9 + ;
 const double eps = 1e-;
 const double pi = acos(-); bool Map[][];
 bool no[];//判断状态i是否不合法
 ll dp[][][];//dp[i][j][k] 表示第i行状态为j，且当前放置的数目为k
 int n, k;
 void init()
 {
     for(int x = ; x < (<<n); x++)
         for(int i = ; i < n - ; i++)
             if((x&(<<i))&&(x&(<<(i+)))){no[x] = ;break;}
     for(int x = ; x < (<<n); x++)if(!no[x])
     {
         for(int y = ; y < (<<n); y++)if(!no[y])
         {
             bool flag = ;
             for(int i = ; i < n; i++)if(x&(<<i))
             {
                 if(y&(<<i)){flag = ; break;}
                 if(i !=  && (y&(<<(i-)))){flag = ; break;}
                 if(i != n && (y&(<<(i+)))){flag = ; break;}
             }
             Map[x][y] = flag;
         }
     }
 }
 inline int f(int x)
 {
     int ans = ;
     for(int i = ; i < n; i++)if(x&(<<i))ans++;
     return ans;
 }
 int main()
 {
     cin >> n >> k;
     init();
     for(int i = ; i < (<<n); i++)if(!no[i])dp[][i][f(i)] = ;
     for(int i = ; i <= n; i++)
         for(int x = ; x < (<<n); x++)if(!no[x])//该行状态
             for(int y = ; y < (<<n);y++)if(!no[y] && Map[y][x])//上一行状态
             {
                 int tmp = f(x);
                 for(int num = ; num + tmp <= k; num++)
                     dp[i][x][num + tmp] += dp[i - ][y][num];
             }
     ll ans = ;
     for(int i = ; i < (<<n); i++)if(!no[i])ans += dp[n][i][k];
     cout<<ans<<endl;
     return ;
 }