Algorithm2.3 状压dp
[TOC]
状压dp
主要特征：n较小 => 暴搜或者状压。【所以主要特征就是可以通过暴力搜索搜出来，但是不能过题，需要用dp，把所有要搜索到的状态压缩到一个01字串中，每个字符都表示】
主要思路：就是将本来某一行的状态是或否的唯二的两种【可能本来需要用数组来储存的】 => 通过用二进制【01来进行储存】
主要原因：用于解决情况之间的耦合性太复杂（就例如八皇后，看上下左右斜上下这些，直接通过压缩成字符串的状态然后来进行位运算即可），如果直接循环遍历去判断的话太麻烦，所以通过状态压缩，
- 把本来是需要用数组表示的数据结构=>用一个字串直接整体表示
- 把本来需要循环来计算的=>用位运算来计算
互不侵犯：https://www.luogu.com.cn/problem/P1896
题目大意：类似于八皇后，只不过八皇后是一行一列都会受影响，而这个题只是相邻的上下行受影响。问放n个皇后最多有多少种方式
1、数据结构：
dp[i][j][s]表示在第i行，且第i行的状态为j时，他所需要的国王的个数为s个，此时的种类数量。
2、遍历层次：遍历各个层->遍历某一层所有的可能的状态->遍历所需要的国王的个数->遍历上一行的状态查看是否冲突sit[j]&sit[t] sit[j]>>1&sit[t] sit[j]<<1&sit[t] ，查看这些状态是否冲突
#include <iostream>
using namespace std;
#define maxn 10
#define maxsit (1<<10)+50
#define maxk 105
int n, k, sit[maxk], cnt_sit, num[maxk]; // dp[i][j][s] 表示在第i行，这一行的状态为j（二进制所转换成的十进制之后的数），放了s个目标 的总方案数
typedef long long LL;
LL dp[maxn][maxsit][maxk], ans=0;
// 首先预处理单独这一行，可能的状态，相互之间不冲突，也就是没有相邻的。【注意是线性的，不是环形的，也就是说101这种的是完全可以的】
void init() {
for (int i = 0; i < (1<<n); ++i) {
if (i & (i<<1)) continue;
int sum = 0;
for (int j = 0; j < n; ++j) if (i & (1<<j)) sum++;
sit[++cnt_sit] = i;
num[cnt_sit] = sum;
}
}
void solve() {
dp[0][1][0] = 1;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= cnt_sit; ++j)
for (int l = num[j]; l <= k; ++l)
for (int t = 1; t <= cnt_sit; ++t)
if (!(sit[j]&sit[t]) && !((sit[j]<<1)&sit[t]) && !((sit[j]>>1)&sit[t])) dp[i][j][l] += dp[i-1][t][l-num[j]];
for (int i = 1; i <= cnt_sit; ++i) ans += dp[n][i][k];
printf("%lld\n", ans);
}
int main() {
scanf("%d%d", &n, &k);
init();
solve();
return 0;
}
类似题目：
https://www.luogu.com.cn/problem/P1123
取数游戏，相邻的八个点不可以拿数，取出的所有数的和最大的情况
*DFS和状压dp的界定：*什么时候用DFS，什么时候用状压dp来处理
炮兵阵地：https://www.luogu.com.cn/problem/P2704
题目大意：一个炮车的左一左二，上一上二，右一右二，下一下二都不能放其他的炮车。问总情况数量
吃奶酪：https://www.luogu.com.cn/problem/P1433
题目大意：问放n个奶酪的最短总路径之和
愤怒的小鸟：https://www.luogu.com.cn/problem/P2831
题目大意：