题目

题目描述

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

注：数据有加强（2018/4/25）

输入输出格式

输入格式：

 

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

 

输出格式：

 

所得的方案数

 

输入输出样例

输入样例#1： 

3 2

输出样例#1： 

16

分析

• 由于上面的种类多，所以我们就要用到状压DP

• 首先，我们要先考虑三个问题
• 上下左右不能放重复
• 上下不能能放重复可以这样解决  直接两行之间and 如果结果为0就是可行的做法
• 左右我们可以讲一行进行>>1和<<1再分别and 查看是否有一个出现为真值的情况
• 在枚举之前先找到所以满足左右的就可以减少时间了
• 最后答案在最后一行全部相加即可

 

代码

 

1 #include
     
       2 using namespace std; 3 long long n,k,t[100001]; 4 long long f[10][100001][101]; 5 long long sta[100001],king[100001],ans; 6 void inte() 7 { 8     int tot=(1<
      
       >=1;    18             }19         }20 } 21 int main ()22 {23     ios::sync_with_stdio(false);24     cin>>n>>k;25     inte();26     for (int i=1;i<=ans;i++)27       if (king[i]<=k)28        f[1][i][king[i]]=1;29     for (int i=2;i<=n;i++)30       for (int j=1;j<=ans;j++)31         for (int kk=1;kk<=ans;kk++)32           {33                if (sta[j]&sta[kk]) continue;34                if (sta[j]&(sta[kk]<<1)) continue;35                if ((sta[j]<<1)&sta[kk]) continue;36                for (int s=1;s<=k;s++)37                {38                    if (s+king[j]>k) continue;39                    f[i][j][king[j]+s]+=f[i-1][kk][s];40                }41           }42     long long sum=0;43     for (int i=1;i<=n;i++)44        for (int j=1;j<=ans;j++)45           sum+=f[i][j][k];46     cout<