原理讲解
状态压缩DP其实就是把一种状态通过二进制的形式储存下来，从而利于进行状态的转移。
例如5个盒子排成一排，其中第1，3，4个盒子有糖果，那么可以表示为 \(10110\) 转换为十进制就是 \(22\) 。
这类问题通常有一定的模板，在以下情况可能要用到状压DP：
- 所输入的内容只有两种状态，就比如只有 \(1\) 和 \(0\) 。
- 统计合法状态的方案数 or 最大值。
不能用其他方法。
解决这类问题的状态一般都设置为如 \(dp_{ij...}\) ,其中 \(i\) 表示第几排/个，\(j\) 表示第 \(i\) 排/个 的状态，如果有其它条件的话可能还需要扩展维度。其状态转移方程一般也类似于 \(dp_{ij}+=dp_{i-1k}\) \(cnt\) 表示合法状态数,当然，其最终答案就类似于 \(\sum_{i=1}^{cnt} dp_{ni}\) ，这肯定不是绝对的，具体还要看是求数量|最大值，还是别的。
那么，状压DP有什么缺点呢？其实也很容易发现：即使是长整型 long long 也只有64位，也就是说最多只能存64和状态，这真是一个致命缺点。
例题解析
理论会了，就开始实践吧！
来看这题 Corn Fields G，这题可以说是超超超经典的一道状压DP题。首先，也是这题的关键，就是将土地状态转化为十进制储存，如将111转化为7。要计算方案总数，那一要先判断那种状态是合法的，判断一种状态是否合法要考虑三个问题，行内合法以，行间兼容，和是否在肥沃的土壤上，也就是这一步体现了题目所说的"位运算的妙用"。
行内兼容
举个栗子：在 \(0000_2 到 1111_2\)中共有8种合法状态 \(0000,0001,0010,0100,0101,1000,1001,1010\)，要怎么筛选出它们呢？回忆一下 & 运算符的运算规则：相同为1否则为零，再往深了想一下是不是只要 i&(i>>1)=0 ,就表明状态 i是合法的？就比如 1010&0101=0。是不是豁然开朗了。 i&(i<<1)=0也是可以的。
行间兼容
有了前面的经验的经验这个就简单了，只要 i$j=0第 \(i\) 行就和第 \(j\) 行相兼容，就比如说 1010&0100=0这两行就可以兼容。
是否在肥沃的土壤上
这个也很好理解，完成这一步骤还是要用到 &运算。
我们来找一下规律：
\(10010\&10000=10000,01100\&10000=0,00000\&10000=0\)
\(10010\&11111=100100,01100\&111111=01100,00000\&11111=0\)
你发现了什么？没错对于土地状态 i和当前状态j 只要 i&j==j,那么状态j就是OK的。
这样就可以愉快的设计算法了:
- 定义 \(dp_{ij}\) 为第
i行第j种状态的方案数。 - 初始状态 \(dp_{1i}=1\),即第1行的每种状态都是一种方案
- 状态转移方程 \(dp_{ij}+=dp_{i-1k}\)
- 最终答案 \(\sum_{i=1}^{cnt} dp_{ni}\)
参考代码
#include<bits/stdc++.h>
using namespace std;
const int mod=100000000;
int num[13],dp[13][1<<13],ans=0;
int g[1<<13];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int tmp; cin>>tmp;
num[i]=(num[i]<<1)+tmp;
}
}
for(int i=0;i<(1<<m);i++){
if(!(i&(i>>1))&&!(i&(i<<1))){
g[i]=1;
if((i&num[1])==i)
dp[1][i]=1;
}
}
for(int x=2;x<=n;x++){
for(int j=0;j<(1<<m);j++){
if(((j&num[x-1])==j)&&g[j]==1){
for(int y=0;y<(1<<m);y++){
if(((y&num[x])==y)&&!(j&y)&&g[y]){
dp[x][y]=(dp[x][y]+dp[x-1][j])%mod;
}
}
}
}
}
for(int i=0;i<(1<<m);i++)
ans=(ans+dp[n][i])%mod;
printf("%d\n",ans);
return 0;
}
更多题目
互不侵犯
炮兵阵地
Matching
Mixed Up Cows G