【本文比较适合有一定动态规划和位运算基础的童鞋阅读】
首先先讲讲什么是状态压缩
状态压缩就是使用某种方法，简明扼要地以最小代价来表示某种状态，通常是用一串01数字（二进制数）来表示各个点的状态。这就要求使用状态压缩的对象的点的状态必须只有两种，0 或 1
我们都知道二进制可以用来枚举子集，例如某个问题有8种情况，那么我们可以一个循环，从0到2^3-1,将所有情况枚举出来，这里拓展一个位运算的技巧（i>>j&1）: 用来求十进制下的数i第j位是否为1，我们规定如果当前位为1就说明这一位应当被选中
动态规划的问题
状态压缩DP常见问题大概可以分为两类
1.棋盘式（基于连通性）DP
2.集合式DP
个人总结的状态压缩dp三部曲：
-
考虑如何状态压缩
- 确定状态表示和状态转移方
- 根据实际问题确定筛选条件 最关键一步！！！合理情况的筛选一定要考虑完全
解释一下第三步的原因，我们状态压缩是对所有情况进行枚举，而实际的题目中会有限制，我们根据题目要求，先对所有情况进行预处理，用一个bool数组，将不合法的数值标记为false即可
例题引入： P1879 [USACO06NOV]Corn Fields G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题意：每一个是1的都可以种植草地，每个草地的上下左右不能有草地，求方案数
第一步：分析如何状态压缩
规定1表示种植草地，0表示不种值，所以每一行的状态由[0,2^m-1]表示，m表示列数
第二步：状态表示和状态转移方程
初状态 f[0][0] = 1（默认一行也不摆也是一种方案）
f[i][j]表示摆完了前i行，第i行的状态是j的方案数
第i行是在前i-1的基础上加上的所以状态转移方程很容易得出：f[i][j] += f[i-1][k];
第三步： 根据实际情况筛选合理情况
本题中要求若中间确定种植草地，则上下左右不允许出现草地，即不允许出现1
我们可以通过位运算来确定是否合法
1.行内合法 位运算技巧： !(i & i >> 1)为真，则为合法情况
技巧讲解： i>>1后i-1位来到了i位，i位来到了i+1位的情况，如果i&i>>1等于0不就是说明i-1和i，i和i+1都是不相等的状态吗，也就是我们当前第i位是1，那么i-1位和i+1位都是0，就保证了左右没有草地
2.行间是否合法
我们假设第i-1行的状态是a,第i行的状态是b,那么需要满足的条件是!(a&b),就是两行间不能有相邻的草地，
3.枚举的状态数是否符合实际的条件
本题的实际条件就是不能超过本行的草地数量
例如一个3行5列的土地，当前行只有两列是可以种植草地的，所以当前土地的草地数为g[i],那么应该满足a&g[i] = a，就是a应该是g[i]的一个子集，相当于a∩g[i] = a
#include<iostream>
using namespace std;
const int mod = 1e9;
int g[14];
int s[1<<14];//s数组用来存储状态，所以列数[1,12]，所以可以开到2^14
int f[14][1<<14];f数组是动态规划的数组，第一维表示行数，第二维表示当前状态
int main()
{
int n,m;
cin>>n>>m;
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
int x;
cin>>x;
g[i] = (g[i] << 1) + x;//位运算
}
}
int cnt = 0;
for(int i = 0;i < (1<<m);i++)
{
if(!(i&i>>1)) s[cnt++] = i;//预处理，将符合条件的状态存下来
}
f[0][0] = 1;//初始
for(int i = 1;i <= n;i++)
{
for(int a = 0;a < cnt;a++)
{
for(int b = 0;b < cnt;b++)
{
if((g[i]&s[a]) == s[a] && !(s[a] &s[b]))//过滤行间和行内要满足的条件
f[i][a] = (f[i-1][b] + f[i][a]) % mod; //状态转移
}
}
}
long long ans ;
for(int i = 0;i < cnt;i++) //遍历所有状态，将第n行的合理状态加起来
{
ans =(ans + f[n][i]) % mod;
}
cout<<ans;
}最后遍历所有的合理状态也可以根据状态转移方程，第n+1的方案是由第n行转移过来的，
所以f[n+1][0] = （f[n][a1] + f[n][a2] + .....f[n][acnt]）,也就是相当于遍历了一遍，所以我们也可以这样写
for(int i = 1;i <= n+1;i++)//循环到第n+1行
{
for(int a = 0;a < cnt;a++)
{
for(int b = 0;b < cnt;b++)
{
if((g[i]&s[a]) == s[a] && !(s[a] &s[b]))
f[i][a] = (f[i-1][b] + f[i][a]) % mod;
}
}
}
cout<<f[n+1][0];例题引入 ：U204941 蒙德里安的梦想 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
第一步 首先先给出一个明显的结论：横放格子的方案数等于总方案数
当竖放的格子确定好位置后，那么横放的格子也就确定了，因为摆放的方式只有横放或者竖放，当竖放确定后，剩余的坑位也就确定了形状，显然这题就是讨论哪个格子是怎么放置的，我们看它给出的数据范围是[1,11]，我们可以考虑按列摆放，那么我们枚举二进制，根据题目实际分析应该是[0,2^m-1],行数是n，那么就有n位。
我们可以规定若某行是1，表示横，某行为0，表示竖放。
第二步
用f[i][j]记录第i列第j个状态。j状态位等于1表示上一列有横放格子，本列有格子捅出来。转移方程很简单，本列的每一个状态都由上列所有“合法”状态转移过来f[i][j] += f[i - 1][k]
初始化条件:f[0][0] = 1第0列只能是状态0，无任何格子捅出来。
终止状态：f[m+1][0]。第m + 1列不能有东西捅出来。
第三步
分析实际情况：
那么在这个题中我们应该可以想到第i列和第i-1不能为同时为1，因为我们规定有1表示当前的列是横放格子的第二个格子，如果i列为1就说明i-1列应该是竖放格子的第一个
所以条件为!(j&k）为真
第二个条件：设当前列的状态是state，,上一列状态为last,我们知道是把行作为状态数，说明这一行有格子，那么我们没有格子的地方最后是要填满竖放格子的，竖放格子的高为2，也就是我们两个放格子的行之间的行数应该是偶数个，如果是奇数个不能放下竖放格子，肯定会有空格，所以state|last 应该是不能出现连续奇数个0，这个条件我们可以通过预处理，将满足条件的状态存下来,下面通过图来解释
绿色为上一列的格子，蓝色表示这一列的格子，last |state 就是两个状态只要出现1，最后的结果的这一行就为1，因为两个状态的交集在第i列，无论是i-1列的状态出现1还是i列出现1，都有第i列肯定有格子，只有两个状态的当前行都为0，第i列的格子才没有被填，所以我们要找的就是 state|last中是否有连续的0
#include<iostream>
#include<cstring>
using namespace std;
const int N = 13,M = 1<<N;
long long f[N][M];
int cnt;
bool st[M];
int main()
{
int n,m;
while(cin>>n>>m,n||m)
{
memset(f,0,sizeof f);
for(int i = 0;i < (1<<n);i++)
{
cnt = 0;
st[i] = true;
for(int j = 0;j < n;j++)
{
if(i >> j & 1)
{
if(cnt & 1)
{
st[i] = false;
cnt = 0;
}
}
else cnt++;
}
if(cnt & 1) st[i] = false;
}
f[1][0] = 1;//初始条件 第一列不能作为横放格子的第二个格子，只有0一种情况
for(int i = 2;i <= m+1;i++)
{
for(int j = 0;j < (1<<n);j++)
{
for(int k = 0;k <(1<<n);k++)
{
if(!(j & k)&& st[j|k]) f[i][j] += f[i-1][k];
}
}
}
cout<<f[m+1][0]<<endl;//第m+1行应该是没有格子的情况
}
}例题引入：P1896 [SCOI2005] 互不侵犯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题意很好理解，就是说如果当前点放了国王，以它为中心的九宫格都不能放置国王
二：状态表示：f[i][j][a]:表示前i行放了j个国王，第i行状态为a的方案数
状态转移：用c数组存储当前行的为a状态时的国王数
f[i][j][a] += f[i-1][j-c[k][b];
三.筛选条件：
1.行内合法：与它左右的方格不能同时放1，!（i&i>>1)为真
2.行间合法：和它的上，左上，右上,下都不能同时放1，!(a&b),!(a&b>>1),!(a&b<<1)都为真时，才可以兼容
#include<iostream>
using namespace std;
long long f[14][144][1<<12];
int nums[1<<12];
int s[1<<12];
int n,cnt;
void init()
{
for(int i = 0;i < (1<<n);i++)
{
if(i&(i>>1)) continue;
s[cnt++] = i;
for(int j = 0;j < n;j++)
{
nums[i] += (i>>j&1);//存储每个状态表示里行间合格的国王数
}
}
}
int main()
{
int k;
cin>>n>>k;
init();//预处理行间
f[0][0][0]=1;
for(int i = 1;i <= n+1;i++)//小技巧：遍历到n+1,那么i+1行的方案数都由i行转移，所有方案都存储在i+1行中
{
for(int j = 0;j <= k;j++)
{
for(int a = 0;a < cnt;a++)
{
for(int b = 0;b < cnt;b++)
{
int c = nums[s[b]];
if(j - c >= 0 && !(s[a] & s[b]) && !(s[a] & (s[b]>>1)) && !(s[a]&(s[b]<<1)))
{
f[i][a][j] += f[i-1][b][j-c];
}
}
}
}
}
// cout<<cnt<<endl;
cout<<f[n+1][0][k];
}例题引入 P2704 [NOI2001] 炮兵阵地 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这道题和第一题十分相似，但是要求是上下左右各多了一格。
状态表示 f[i][a][b] :第i行的状态为a，i-1行状态为b。
状态转移 f[i][a][b] 是由上一行f[i-1][b][c]转移而来。
筛选条件
1.行内：!(i&i>>2）和!(i&i>>1)同时为真
2.行间 a,b,c相与必须为0文章来源：https://www.toymoban.com/news/detail-493676.html
3.不能在山地上布署文章来源地址https://www.toymoban.com/news/detail-493676.html
#include<iostream>
using namespace std;
int g[110];
int cnt;
int num[1<<10];
int s[1<<10];
int f[2][1<<10][1<<10];
int main()
{
int n,m;
cin>>n>>m;
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
char ch;
cin>>ch;
int x = 0;
if(ch == 'P') x = 1;
g[i] = (g[i]<<1) + x;
}
}
for(int i = 0;i < (1<<m);i++)
{
if(!(i & i >>1)&&!(i & i >>2))
{
s[cnt++] = i;
for(int j = 0;j < m;j++)
{
num[i] += (i >> j & 1);
}
}
}
// cout<<cnt<<endl;
//f[0][0][0] = 1;
for(int i = 1;i <= n +2;i++)
{
for(int a = 0;a < cnt;a++)
{
for(int b = 0;b < cnt;b++)
{
for(int c = 0;c < cnt;c++)
{
if(!(s[a]&s[b]) && !(s[a]&s[c]) && !(s[b]&s[c]) && (g[i-1]&s[b])==s[b] &&(g[i]&s[a])==s[a])
{
f[i&1][a][b] = max(f[i&1][a][b],f[i-1&1][b][c]+num[s[a]]);
}
}
}
}
}
cout<<f[n+2&1][0][0];
return 0;
}到了这里，关于一文带你入门并吃透状态压缩DP的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
