题目描述

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

左下右上右下八个方向上附近的各一个格子，共8个格子。

输入

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

输出

　　方案数。

样例输入

3 2

样例输出

16

 

 

　　n<=9，显然是状压dp，定义状态f[i][j][k]表示枚举到第i行，状态为j，前i行总共放了k个国王的方案数。搜索出一行符合的所有状态，枚举当前行和上一行的状态，判断是否冲突，然后f[i][j][l]+=f[i-1][k][l-t[j]]转移即可。最后答案是∑f[n][j][m]

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;long long f[12][2000][200];int cnt;int n,m;int s[2000];int t[2000];long long ans;void dfs(int x,int y,int sum){ if(y>=n) { s[++cnt]=x; t[cnt]=sum; return ; } dfs(x,y+1,sum); dfs(x|(1<