状压dp

视频链接
（如果想购买网课，可以用我的邀请码）
用我的链接购买，我再反你10，一共花54多值
购买链接
不放心可以先加我好友2830872914

总试题链接

文章目录

• • 状压dp
  • 预备知识——位运算
• 例题：
• • 引入：
  • NC20240 [SCOI2005]互不侵犯
  • NC16886 炮兵阵地
  • TSP问题 NC16122郊区春游 NC16544简单环
  • NC15832 Most Powerful
  • 棋盘覆盖 poj2411 NC107008 Mondriaan's Dream
  • 总结：
• 习题：
• • NC14732 锁
  • NC15034 德玛西亚万岁
  • NC16418 宝藏
  • NC17061 多彩的树
  • NC17890 方格填色
  • NC20485 [ZJOI2009]多米诺骨牌

预备知识——位运算

当做01串处理
<< 左移（有可能溢出）
.>> 右移（最后一位丢掉）
| 或
& 和
^ 异或（相同为0，不同为1）
~ 取反
操作：
去掉最后一位：x>>1
在最后加上一个0：x<<1
在最后加一个1：（x<<1）+1
把最后一位变成1：x | 1
把最后一位变成0：（x|1）-1
最后一位取反：x^1
把从右边数第k位变成1：x | (1<<(k-1))
把从右边数第k位变成0：x&（~（1<<(k-1)））
把右数第k位取反：x^(1<<(k-1))
取末k位：x&((1<<k)-1）
取右数第k位（x>>(k-1)）&1
把末k位变成1:x|((1<<k)-1)
末k位取反:x^((1<<k)-1)
把右边连续的1变成0: x&(x+1)
把右边第一个0变成1: x|(x+1)
把右边连续的0变成1： x|(x-1)
去右边连续的1：(x^(x+1))>>1
去掉右边第一个1的左边：x&(-x)

例题：

引入：

在n*n的方格上放n个车，它们不能在同一行列，问总方案数
方法：阶乘 n！

添加要求：某些格子不能放
方法：
取棋子的放置情况当做状态，放则为1，不放为0
n=5，第1,3，4已经放置，状态就是01101（从右向左）
dp[i][st]表示前i行的状态为st的方法数
dp[i][st]=∑dp[i-1][st’]
st理解成01串
st’与st关系满足：(st’ & (1<<(j-1)))==0 && st’ +(1<<(j-1)) = = st
st’中第j列没有放，并且st’放上第j列后就等于st
st’=0 0 1 0 1
然后放在第四列
st=0 1 1 0 1

NC20240 [SCOI2005]互不侵犯

题解链接
题目：n*n的方格放k个车，车之间不能靠着，问多少种方法？
题解：
需要知道前一行的情况，所以一行一行的放车
记录每行的情况
在本题中，不能存在相邻的1
对于一行x：
(x&(x<<1))==0—–>可以判断左右是否有相邻的1
对于上一行x，下一行y：
(x&y）= = 0
(x&(y<<1)) = =0
(x&(y>>1)) = = 0
上下，左下，右下都不为0
dp[i][j][k]表示第i行状态为k，已经放了j个车
转移方程：
dp[i][j][k]+=dp[i-1][j-num[k]][p]
(k&p) = = 0
(x&(p<<1))= =0
(x&(p>>1))= =0
num[k]表示k状态的国王数

NC16886 炮兵阵地

题解链接
题目：
n*m个网格，有平原，有山地，平原可以放部队，部队攻击范围如图（不受地形影响）

在防止误伤的情况下，最多能放多少炮兵部队
题解：
确定状态：
因为每个炮可以打到两行，所以每一行放置方式与他放置的情况有关
dp[i][j][k]表示第i行为状态j，第i-1行为状态k时所用的最大炮兵数
也就是同时记录两行状态，根据已知的两行状态推下一行
状态转移：
dp[i][j][p]=max(dp[i][j][p],dp[i-1][p][q]+num[j])
q被枚举
第i行状态：j
第i-1行状态：p
第i-2行状态：q
j，p，q不能发生冲突
任意1左右两边两位都不是1
((i&(i>>1))==0) && ((i&(i>>2)) ==0)
且1的位置必须是平原
优化：保存符合条件的二进制串，只枚举自身符合要求的二进制串

TSP问题 NC16122郊区春游 NC16544简单环

郊区春游题解链接
简单环题解链接
题目：
给定一张图，求从某个起点出发，经过所有的点的最短路径（每个点经过且只经过一遍）
题解：
dp[st][i]表示当前状态st，最后到达的一个点是i，所经过的最短路径
st是01串，1表示该点走过
状态转移：
dp[st][i]=minn(dp[st’][j]+a[j][i])
st’+(1<<(i-1))==st
st’&(1<<(i-1))==0
st’第i位是0
st第i位是1
扩展
如果要求走完所有的点回到原点怎么办？
dp[111111][？？]
？？：1—>n
加上1到起点的距离，2到起点的距离…，比较哪个最佳

NC15832 Most Powerful

题解链接
题目：
不超过十种气体，两两碰撞产生一定能量，a碰b，b就会消失，不能自身碰，问最后得到的最大能量
题解：
确定状态：
dp[i]表示状态i时所能获得的最大能量
i的第k位为1，则说明第k个气体已经用了并消失。为0则说明没用或是用了没消失
状态转移：
dp[k|(1<<(i-1))]=max(dp[k]+a[j][i])]
用当前状态k推出新状态（状态是往前看）
k|(1<<(i-1))：k的第i位变为1，第i个气体没了
i和j均要枚举

答案dp[x]:x为只有一个0的01串

棋盘覆盖 poj2411 NC107008 Mondriaan’s Dream

题解链接
题目：
n * m的矩阵，用1 * 2和2 * 1的砖快密铺，问多少种方法：


竖向砖块我们上面填0，下面填1
上下两行状态做&操作，为0的位置就是竖向砖块的下边沿，剩下的1就是下边砖块的，相邻的1是否为偶数个，如果是偶数个说明可以填满，否则不合理
（太难了~ ~ ~）

总结：

把复杂的情况压缩，将一个状态压缩成一个整体
hash过程
什么问题用状压dp：
在棋盘格子上覆盖，有一维不是很大即可
类似于TSP的路径问题
N比较小，变成n位二进制后还很合理

习题：

题目链接

NC14732 锁

NC15034 德玛西亚万岁

NC16418 宝藏

NC17061 多彩的树

NC17890 方格填色

NC20485 [ZJOI2009]多米诺骨牌

创作挑战赛新人创作奖励来咯，坚持创作打卡瓜分现金大奖