题解：P1896 [SCOI2005] 互不侵犯
TH911
·
·
题解
个人Blog同步链接
题目传送门
什么是状压DP
状压 DP 是动态规划的一种，通过将状态压缩为整数来达到优化转移的目的。
——OI Wiki
状态压缩
例如，给定一个 bool 数组 c，那么 c_i 为 0 或 1。
我们可以将其压缩为一个二进制整数 (a)_2，这样 a&(1<<i) 即 c_i。可以参照下表：
| i |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
| c_i |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
a&(1<<i) |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
此时，(a)_2=(10011010)_2,a=154。
状压DP
在此基础上进行DP，状态的转移化为了整数，那么状态转移同样得到了优化（位运算）。
设计状态压缩
首先，这是一个 N\times N 的棋盘。
那么，我们考虑压缩一行为一个整数。（当然，压缩列同样可行，你只需要“将棋盘转 90^\circ”）
# 考虑状态转移
我们定义 $dp[i][j][k]$ 表示：
* DP至第 $i$ 行；
* 共放置了 $j$ 个国王（由于题目给出“放置 $K$ 个国王”）；
* 第 $i$ 行状态为 $k$（因为国王**会影响到下一行的状态**）。
一个很明显的结论是国王周围 $8$ 个格子内**不能**有其他国王（如图）。
蓝色为国王，红色为不能走区域（橙色为红色重合部分），绿色为其他国王可以放置的位置。
## 行内预处理
我们可以**先处理行内不可能存在的情况**：行内国王**相邻**。
也就是说，状态 $S$ 内不能存在两个二进制位 $1$ 相邻。
那么我们便可以通过 `(S<<1)|S` 判断（假设 $S=(110101)_2$）：
| **`S`** | **0** | **1** | **1** | **0** | **1** | **0** | **1** |
| :--------: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| **`S<<1`** | **1** | **1** | **0** | **1** | **0** | **1** | **0** |
不难发现，如果此时有 $1$ 在同一列，那么 $S$ 便会有相邻的 $1$。
事实上，使用 `(S>>1)|S` 也是可行的，**但这不重要**。因为两个相邻的 $1$，无论左移还是右移，都是从**至少**两位 $1$ 重合变为**至少一位 $1$ 重合**。
所以，当一个状态 $S$ 满足 `(((S<<1)|S)&1)==0` 时，这一行才**可能**成立，其余情况**可以直接忽略**。
于是，开一个 $ok$ 数组记录，$ok[i]$ 表示第 $i$ 大的**合法行**。
其实还需要预处理一个 $cnt[S]$ ，具体后文会提到。
## 行间转移
处理完了行内，现在开始处理行间状态转移。
如果第 $i-1$ 行第 $j$ 号位置有一个国王，那么第 $i$ 行第 $j-1,j,j+1$ 号位置都**不能**有国王。
不妨令第 $i$ 行状态为 $S1$，第 $i-1$ 行为 $S2$。
同样的，由于我们进行了状态压缩，也就是当状态满足 `((S2<<1)&S1)==0&&(S2&S1)==0&&((S2>>1)&S1)==0` 时，第 $i$ 行才**有可能**为状态 $S1$。
对条件进行简写：`(((S2<<1)|S2|(S2>>1))&S1)==0`。
转移方程至此也就很好理解了：
$$
dp[i][j][S1]=\sum_{j=cnt[S1]}^k{dp[i-1][j-cnt[S1]][S2]}
$$
其中，$cnt[S1]$ 表示**二进制整数** $S1$ 中 $1$ 的个数，已经预处理过。
# DP边界
$$
dp[0][0][0]=1
$$
很好理解，就是第 $0$ 行无法处理，只能放置 $0$ 个国王，第 $-1$ 行无法放置国王。
~~但是，事实上多数情况都是为了运算方便而如此设计的。~~
# 统计答案
首先 $dp$ 数组的前两维很好判断，就是 $n,k$。那么第三维，第 $n$ 行的状态我们是不知道的。事实上为了统计所有可能数，第 $n$ 行什么状态都有可能，因此我们一个一个枚举累加即可。
# 注意事项
1. ***开 `long long`！开 `long long`！开 `long long`！***
***重要的事情说三遍。***
2. **数组大小**
$dp$ 需要开到 $dp[N+1][K+1][2^{N+1}]$。
其中 $N,K$ 需要取最大值 $N=9,K=N^2=81$。（$2^N$ 使用 `1<<N`，而不是 `pow(2,N)`）
$ok,cnt$ 都需要开到 $2^{N+1}$。
考虑到数据范围 $N\leq9$，并不会 $\text{MLE}$。
3. **运算优先级**
参见[OI Wiki](https://oi-wiki.org/lang/op/#c-%E8%BF%90%E7%AE%97%E7%AC%A6%E4%BC%98%E5%85%88%E7%BA%A7%E6%80%BB%E8%A1%A8)，**可以发现 `&`、`^`、`|` 这三个位运算符的优先级低于 `==` 等关系运算符**。因此，建议对于位运算符，尽量都**加上括号保证运算顺序正确**。
# AC代码
```cpp
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
const int N=9,K=N*N;
int n,k,top;
//1:国王,0:空置
//cnt[i]:i在二进制下的 1 的个数
//ok[i]:第i个行内1不相邻的状态
//dp[i][j][k]:第i行,共放置j个国王,第i行是状态k
ll cnt[(1<<N+1)+1],ok[(1<<N+1)+1],dp[N+1][K+1][(1<<N+1)+1];
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
scanf("%d %d",&n,&k);
//预处理:cnt,ok.
for(int i=0;i<(1<<n);i++){
int pl=0,j=i;
while(j){
if(j&1)pl++;
j>>=1;
}cnt[i]=pl;
if(((i<<1)&i)==0)ok[++top]=i;
}//边界
dp[0][0][0]=1;
for(int i=1;i<=n;i++){
//p,q:枚举第i行,第i-1行的状态
//[1,top]优化,剔除行内不满足的
for(int p=1;p<=top;p++){
int s1=ok[p];
for(int q=1;q<=top;q++){
int s2=ok[q];
//行间合法
if((((s2<<1)|s2|(s2>>1))&s1)==0){
//DP累加
for(int j=cnt[s1];j<=k;j++){
dp[i][j][s1]+=dp[i-1][j-cnt[s1]][s2];
}
}
}
}
}//输出
ll ans=0;
for(int i=1;i<=top;i++)ans+=dp[n][k][ok[i]];
printf("%lld\n",ans);
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
```