状压dp
四川2005年省选题：互不侵犯
首先我们可以分析一下，按照我们普通的思路，就是用搜索，枚举每一行的每一列，尝试放下一个国王，然后标记，继续枚举下一行
那么，我们的时间复杂度就拥有了：
O
(
9
9
)
O(9^9)
O(99)
计算方法：
因为是 n × n n\times n n×n 的棋盘，所以每行都会有至多9列（ n ≤ 9 n\le 9 n≤9）
然而我们每行都会有 n n n 种状态，所以我们的时间复杂度就是 O ( n n ) O(n^n) O(nn) ，即 O ( 9 9 ) O(9^9) O(99)
不过嘛——
所以我们是肯定不能采用的
这个时候，我们就需要学到一个 鬼东西 ——状态压缩dp！！
状压dp介绍——
所谓状压，字面翻译，就是把 复杂的状态 简化为 简洁的n进制数来表示
例如这道题
因为dp的状态转移，无非就是放和不放，所以我们就可以很容易地想到，用二进制的01串来表示，例子——
010001000
表示在第2列和第6列放国王，其余不放。
而 ( 010001000 ) 2 (010001000)_2 (010001000)2 = ( 136 ) 10 (136)_{10} (136)10
因为 n ≤ 9 n\le 9 n≤9 ，所以这个数 ≤ 2 9 \le 2^9 ≤29 即 ≤ 512 \le 512 ≤512
那么我们需要进行一下判断，即满足什么条件时，可以放置这个国王
条件判断：
首先因为是二维的关系，我们先来判断行的关系，即一行一行地判断，看看上一行所放置的国王，限制了这一行哪些国王的放置
扫雷都玩过吧，附近的八个格子，设国王放置在 (x,y) 的地方，我们将它简化为以下关系：(x为行，y为列)
(
x
−
1
,
y
−
1
)
(
x
−
1
,
y
)
(
x
,
y
+
1
)
(
x
,
y
−
1
)
(
x
,
y
)
(
x
,
y
+
1
)
(
x
+
1
,
y
−
1
)
(
x
+
1
,
y
)
(
x
+
1
,
y
+
1
)
(x-1,y-1)\ \ \ \ \ (x-1,y)\ \ \ \ \ (x,y+1) \\ (x,y-1)\ \ \ \ \ (x,y)\ \ \ \ \ (x,y+1) \\ (x+1,y-1)\ \ \ \ \ (x+1,y)\ \ \ \ \ (x+1,y+1)
(x−1,y−1) (x−1,y) (x,y+1)(x,y−1) (x,y) (x,y+1)(x+1,y−1) (x+1,y) (x+1,y+1)
显然，如果上一行的 i 列放置了国王，那么下一行的 i-1,i,i+1 都不可以放置
那么如何判断呢
我们不难想到二进制的 左移右移运算符 ，目的是可以将目标 i 移到左于右的地方，进行判断
判断方法：
如果我们这一行的第 j 列需要放国王，那么上一行的 (i<<1),(i>>1),i 都不可为1，那么我们就可以运用位运算符 & 。有一位是1答案就为1，换句话说，只要 上下行同列放了两个国王 ，就不合法
再来说下列的关系
如果在同一列，左移右移旁边都没有，则是合法的（具体可以联系行的关系进行思考）
那么我们应该如何设用来dp的 f 数组， 状态转移方程 又该怎么写呢
我们不难想到可以一行一行的枚举（上文已提到），即设 f 数组 f[i][j][l] 表示现在在第 i 行，已经放了 j 个国王，所有方案为 l （这就是状压dp的精髓所在）
状态转移方程：
f ( i , j , l ) = ∑ f ( i − 1 , x , l − s t a ( j ) ) f(i,j,l)=\sum f(i-1,x,l-sta(j)) f(i,j,l)=∑f(i−1,x,l−sta(j))
代码（加过注释的）：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=15,MAXM=85,MAXS=(1<<9)+5;
int n,k;
ll f[MAXN][MAXM][MAXS],ans;
int cnt,tmp,tot;
int num[MAXS],s[MAXS];
int s1,s2;
int main(){
scanf("%d%d",&n,&k);
f[0][0][0]=1;
for(int i=0;i<(1<<n);i++)
{
cnt=0,tmp=i;
while(tmp)
{
if(tmp&1) ++cnt;//cnt统计i的二进制有放了多少国王
tmp=tmp>>1;//继续枚举
}
num[i]=cnt;//num[i]表示第i种状态有num[i]个国王放在那里
if(!(((i<<1)|(i>>1))&i)) s[++tot]=i;//判断行内放国王合不合法,比较抽象
}
for(int i=1;i<=n;i++)//遍历每一行
{
for(int j=1;j<=tot;j++)//枚举这一行每种可能的状态
{
s2=s[j];//s2代表这一行的状态
for(int l=1;l<=tot;l++)//前一行的每种状态
{
s1=s[l];//s1代表上一行的状态
if(!(s1&s2)&&(!((s1<<1)&s2))&&(!((s1>>1)&s2)))//行间的限制判断
for(int a=0;a<=k;a++)
if(a-num[s2]>=0)
f[i][a][s2]+=f[i-1][a-num[s2]][s1];
}
}
}
for(int i=1;i<=tot;i++)
ans+=f[n][k][s[i]];
printf("%lld\n",ans);
return 0;
}
