[SCOI2005]互不侵犯（状压DP）

https://www.luogu.com.cn/problem/P1896

题目描述

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

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

输入格式

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

输出格式

所得的方案数

输入输出样例

输入 #1

3 2

输出 #1

题目十分简短：观察数据范围我们可以知道：这题有庞大的状态量，所以我们就用状压DP解决问题

dp思路：三维，第一维表示行数，第二维表示第j个可行状态，第三维表示已经放了的棋子数（这类题都有套路的，有数量限制的dp一般都要多开一维表示用了的数量）

 1 #include <bits/stdc++.h>
 2 typedef long long LL;
 3 const int INF=0x3f3f3f3f;
 4 const double eps =1e-8;
 5 const int mod=1e8;
 6 const int maxn=1e5+10;
 7 using namespace std;
 8 
 9 LL dp[10][1050][105]; //第一维表示行数，第二维表示第j个可行状态，第三维表示已经用了的棋子数
10 int need[1050]; //第i个可行状态中1的个数 
11 int state[1050]; //第i个可行状态是多少 
12 int cnt;
13 
14 void init(int n)
15 {
16     for(int i=0;i<(1<<n);i++)
17     {
18         if(i<<1 & i) continue;
19         state[++cnt]=i;
20         int t=i;
21         while(t)
22         {
23             need[cnt] += t%2;
24             t>>=1; //相当于t/=2; 
25         }
26     }
27 }
28 
29 int main()
30 {
31     #ifdef DEBUG
32     freopen("sample.txt","r",stdin);
33     #endif
34     
35     int n,m;
36     scanf("%d %d",&n,&m);
37     init(n); //初始化，别忘了 
38     for(int i=1;i<=cnt;i++) //先处理第一行
39     {
40         if(need[i]<=m) dp[1][i][need[i]]=1;
41     }
42     for(int i=2;i<=n;i++) //处理剩下的，所以从 2 开始枚举
43     {
44         for(int j=1;j<=cnt;j++) //枚举状态
45         {
46             for(int k=1;k<=cnt;k++) //枚举上一层的状态
47             {
48                 if(state[j]&state[k]) continue; //上下不能相邻
49                 if((state[k]<<1)&state[j]) continue; //本行的右上角不能有棋子 
50                 if((state[k]>>1)&state[j]) continue; //本行的左上角也不能有棋子 
51                 for(int g=m;g>=need[j];g--)
52                     dp[i][j][g]+=dp[i-1][k][g-need[j]];
53             }
54         }
55     }
56     LL ans=0;
57     for(int i=1;i<=cnt;i++)
58         ans+=dp[n][i][m];
59     printf("%lld
",ans);
60     
61     return 0;
62 }