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

时间：2023-11-15 11:57:14

题目链接：

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 ;

 }

相关文章