在被Macw的排位赛#13第7题拿捏后,我不得不去烹调一波状压DP,现做出此文,教大家食用状压DP。
这是个好东西,学会了可以做好多绿题和蓝题
阅读此文前,你需要自学DP、进制数以及位运算的基本知识等。
好,进入正文!
NO.1 前置知识
状压DP(状态压缩动态规划)是一种特殊的动态规划方法,它将状态压缩为二进制整数来表示,以便更有效地进行状态转移和优化。
好!看完后,我们知道,状压DP=状压(状态压缩)+DP(动态规划);
DP就先不介绍了,接下来让我们先谈谈状态压缩。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
NO.2 状态压缩
状态压缩是一种将“物品”状态通过 nnn 进制数表示的技巧(nnn 为状态数, 一般较小,通常为 222)。通常用一个整数其 nnn 进制中的第 iii 位上的数来表示第 iii 个“物品”的状态,状态压缩的核心在于使用位运算来处理和比较。
比如:二进制可以用于表示棋盘上一行的格子是否有棋子(有无,共 222 种)、硬币的正反面(正反,共 222 种)、该物品取不取(是否取,共 222 种)等。
比如我们有一行 888 个方格,在方格里填充 000 和 111 ,那么总的方案数就应该有 282^828 个。我们现在使用状态压缩,将 888 个方格看成 888 位, 000 和 111 都看成二进制,那么这 888 位就组成了一个二进制数。比如0001 0010转成十进制就是 181818 ,它表示从右往左第 222 和第 555 个方格里是 111。
例题1:充满希望的拼接质数1
我们假设 nnn 为 444,考虑一个状态 xxx ,这个 xxx 的二进制取值范围在0001~1111之间,二进制从右往左第 iii 位为 111 表示取第 iii 块水晶;
那么我们可以枚举 111 ~ (24−1)(2^4-1)(24−1)的区间,即枚举二进制0001~1111这个区间里的所有状态,然后求出状态 xxx 中取的水晶之和,最后判断质数即可。
例题2:披萨店
和上题差不多,我们输入时可以用一个 vectorvectorvector 存储会产生冲突的披萨,仍然枚举所有状态,判断一个状态中会不会产生冲突,否则答案加 111 ,具体看代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
NO.3 位运算的小技巧
为了方便接下来的理解,我们先来学习些位运算的小技巧:
代码 作用 n&1 判断n是否为奇数 n&m 判断n和m二进制中是否有同为一的位置 n&(n-1) 消去n二进制中最右侧的1 n>0&&(n&(n-1))==0 检查n是否为2的幂次方 n&(-n) n的最右边一个1的位置对应的数 n&(1<<(i-1))或n>>(i-1)&1 判断n的第i位是否为1(输入时从1开始) n&(~(1<<(i-1))) 去掉n的第i位的1(输入时从1开始) n^(1<<(i-1)) 将n的第i位取反 n or (1<<(i-1)) 将n第i位变为1 ⋅⋅⋅⋅⋅⋅······⋅⋅⋅⋅⋅⋅ ⋅⋅⋅⋅⋅⋅······⋅⋅⋅⋅⋅⋅
例题1:高低位交换
我们可以用x<<16让 xxx 的后 161616 位移到前面去,原来的前 161616 位会溢出;
我们可以用x>>16让 xxx 的前 161616 位移到后面去,原来的后 161616 位会溢出;
两个相加即可。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
NO.4 状压DP
接下来我们回到状压DP。
状压DP:顾名思义,就是用状态压缩实现DP;
状压DP主要分为棋盘式和集合式:
* 棋盘式:主要用于处理棋盘类问题,通过状态压缩来表示棋盘上每个格子的状态(如是否有障碍物、是否被占用等)。这种方法常用于解决如迷宫问题、棋盘游戏等问题;
* 集合式:用于表示一个集合中的元素是否被选择。这种方法适用于处理如背包问题、选择问题等,通过二进制数来表示集合中的元素状态,每个二进制位对应集合中的一个元素,1表示选择该元素,0表示不选择。
4.1 棋盘式:
例题1:[SCOI2005] 互不侵犯
首先,我们根据之前的经验,考虑枚举一行的所有状态,即从 000 ~ (2N−1)(2^N-1)(2N−1) 枚举一遍,判断合法的状态,用一个数组存下来,并存储 iii 状态中放的国王数量;
那,怎么判断合法呢?怎么算放的国王数量呢?这就要用到上文说的一些技巧了:
这样就可以预处理所有的状态了:
接下来,我们考虑DP:
1. 状态:dp[i][j][k]dp[i][j][k]dp[i][j][k]表示第 iii 行状态为 jjj ,当前共放了 kkk 个国王的方案数;
2. 转移方程:由于当前状态可以由上一行所有不会产生冲突的状态转移而来,所以状态转移方程为
dp[i][j][l]=∑i=1Ldp[i−1][l][g−cnt[j]]dp[i][j][l]=\sum_{i=1}^{L} dp[i-1][l][g-cnt[j]] dp[i][j][l]=i=1∑L dp[i−1][l][g−cnt[j]]
其中, iii 表示当前第 iii 行,jjj 表示当前状态,lll 表示上一状态, ggg 表示当前放的国王总数,LLL 和 cntcntcnt数组见上文;
3. 初始条件:由于 dpdpdp 数组需要由上一行得到,所以我们需要初始化 dpdpdp 数组的第一行,而 dpdpdp 数组第一行的方案即所有合法的状态,所以在枚举合法方案时初始化即可,dp[1][L][cnt[L]]=1;;
4. 循环顺序:我们第一层循环 iii ,表示第 iii 层,第二层循环 jjj,枚举当前状态,第三层循环 lll,枚举上一行状态,如果状态 jjj 和状态 lll 不会产生冲突,那么循环 ggg ,从 cnt[j]cnt[j]cnt[j] (至少有当前状态放的国王数量)到 kkk (数量上限),枚举当前放的国王总数;
5. 显而易见,答案是 dpdpdp 数组中第 nnn 行放 kkk 个国王的所有状态的方案之和,即
∑i=1Ldp[n][i][k]\sum_{i=1}^{L} dp[n][i][k] i=1∑L dp[n][i][k]
那么DP自然就出来了
最后贴一波代码:
例题2:
[USACO06NOV] Corn Fields G
Acwing.玉米田
乌龟养殖场
额,好好好,这么玩是吧(我赛时咋没发现),这几题差不多(差别在有的可以一个都不放),所以这里具体就讲[USACO06NOV]CornFieldsG[USACO06NOV] Corn Fields G[USACO06NOV]CornFieldsG这题。
这一题和上一题差不多,但少了个数限制,且冲突条件变了。
所以我们先来想想如何存图。这一题里,图显然只会在判断第 iii 行状态是否有在不适合种草地方种草,怎么判断呢?如果把牧场第 iii 行的土地状况存储为一个状态 mp[i]mp[i]mp[i],当前状态为 jjj,我们可以用(~mp[i])&j来判断。为什么?~mp[i]会把第 iii行不适合种草的地方标记为 111,肥沃的反标记为 000,而(~mp[i])&j有值则说明~mp[i]中有些 111 的位置状态 jjj 中也为 111,即在不适合种草的地方种了草,所以不成立。那既然会用到~mp[i],那么我们输入时就可以把 mpmpmp 数组取反,这样就不用后面取反了。
那这样就可以存图了:
接下来为了存储所有合法状态,我们来想想怎样判断状态合法。
有了上题的经验,当前状态若为 iii,那么i&(i<<1)有值则说明当前状态中有连续的 111,即有些种草的地旁边也有草,不成立;
上行状态为 jjj,若i&j有值则说明两行中有位置都是 111,即都种了草,不成立。
存储所有合法状态时用i&(i<<1)判断就可以了:
我们接下来再考虑DP:
1. 状态:dp[i][j]dp[i][j]dp[i][j]表示第 iii 行状态为 jjj 的方案数;
2. 转移方程:由于当前状态可以由上一行所有不会产生冲突的状态转移而来,所以状态转移方程为
dp[i][j]=dp[i−1][k]dp[i][j]=dp[i-1][k] dp[i][j]=dp[i−1][k]
其中, iii 表示当前第 iii 行,jjj 表示当前状态,kkk 表示上一状态;
3. 初始条件:由于 dpdpdp 数组需要由上一行得到,所以我们也可以初始化第0行放一个的情况:dp[0][1]=1;;
4. 循环顺序:我们第一层循环 iii ,表示第 iii 层,第二层循环 jjj,枚举当前状态,第三层循环 kkk,枚举上一行状态即可;
5. 显而易见,答案是 dpdpdp 数组中第 nnn 行放 kkk 个国王的所有状态的方案之和,即
ANS=∑i=1Ldp[n][i]ANS=\sum_{i=1}^{L} dp[n][i] ANS=i=1∑L dp[n][i]
最后放一下代码:
例题3:骨牌铺法/蒙德里安的梦想
和前面不同,我们考虑按列放置(即状态表示竖列)。
对于一个状态,我们把 000 记为竖放, 111 记为横放;
那么,一个状态中若有连续的 000 的个数为奇数,则不成立(因为 000 为竖放,而竖放一块骨牌会占 222 格,若连续 000 的的数量为奇数,说明有半块骨牌),所以我们可以筛选所有合法的状态:
那么我们接下来考虑DP:
1. 状态:dp[i][j]dp[i][j]dp[i][j]表示第 iii 列状态为 jjj 的方案数;
2. 转移方程:由于当前状态可以由上一列所有不会产生冲突的状态转移而来,
那怎么判断合法呢?首先,把两列合并,上列横放(111),当前列必为空(000);上列竖放,这列为竖放或横放(111或000),所以,两行合并合法,则(j&k)==0;其次,如上述,j|k为111必定是两列有一个横放,为000则必定是两列都竖放,我们上面预处理过,连续的 000 的个数不为奇数则成立,即state[j|k]。
所以状态转移方程为
dp[i][j]=∑i=0Ldp[i−1][k]dp[i][j]=\sum_{i=0}^{L} dp[i-1][k] dp[i][j]=i=0∑L dp[i−1][k]
其中, iii 表示当前第 iii列,jjj 表示当前状态,kkk 表示上一列状态;
3. 初始条件:我们可以初始化第0列一个也不放的情况:dp[0][0]=1;;
4. 循环顺序:我们第一层循环 iii ,表示第 iii 列,第二层循环 jjj,枚举当前状态,第三层循环 kkk,枚举上一列状态即可;
5. 由于数组最后一列无法横放,所有答案是 dp[m][0]dp[m][0]dp[m][0]。
最后放一下代码:
补充题:
[NOI2001] 炮兵阵地
剑之试炼
4.2 集合式:
例题1:吃糖
对于每一包糖,我们可以用a[i]|=(1<<(w-1))把第 iii 包糖压缩为一个状态,便于我们完成“吃糖”的操作,所以:
接下来考虑DP:
1. 状态:我们用dp[i]dp[i]dp[i]表示 iii 状态下选的最少的糖包数;
2. 转移方程:iii 状态下选择第 jjj 包糖的方案可以由当前状态转移,即:
dp[i∣a[j]]=min(dp[i∣a[j]],dp[i]+1);dp[i|a[j]]=min(dp[i|a[j]],dp[i]+1); dp[i∣a[j]]=min(dp[i∣a[j]],dp[i]+1);
其中i|a[j]表示iii 状态下选择第 jjj 包糖后的状态,dp[i]+1dp[i]+1dp[i]+1表示当前又选了一包糖;
3. 初始条件:初始化每一包糖:dp[a[i]]=1;,什么也不放:dp[0]=1;
4. 循环顺序:我们第一层循环 iii ,枚举状态,第二层循环 jjj,枚举当前糖果即可;
5. 如果dp[1<<m−1]dp[1<<m-1]dp[1<<m−1]没有更改,则说明无法凑齐 mmm 包糖,输出 −1-1−1;否则输出dp[1<<m−1]dp[1<<m-1]dp[1<<m−1]。
最后放个代码:
例题2:小猫爬山
[USACO12MAR]Cows in a Skyscraper G
两题一样(都也可以用记搜做),这里讲小猫爬山。
此题有两个因素:当前缆车剩余承重与缆车数,所有我们分别用两个数组记录;
接着考虑装态:状态 iii,111 表示猫已上缆车,000 表示未上缆车;
最后考虑DP:‘
1. 状态:我们用dp[i]dp[i]dp[i]表示 iii 状态下使用的最少的缆车数,用c[i]c[i]c[i]表示 iii 状态下所有的缆车中最大的剩余承重(贪心);
2. 转移方程:i|[a[j]表示该猫上缆车后的状态,然后dpdpdp由当前状态转移最小值(更小的缆车数量),ccc由当前转移最大值(更大的剩余承重)分两种情况 :
一、能放 :
dp[i∣(1<<(j−1))]=min(dp[i∣(1<<(j−1))],dp[i])dp[i|(1<<(j-1))]=min(dp[i|(1<<(j-1))],dp[i]) dp[i∣(1<<(j−1))]=min(dp[i∣(1<<(j−1))],dp[i])
c[i∣(1<<(j−1))]=max(c[i]−a[j],c[i∣(1<<(j−1))])c[i|(1<<(j-1))]=max(c[i]-a[j],c[i|(1<<(j-1))]) c[i∣(1<<(j−1))]=max(c[i]−a[j],c[i∣(1<<(j−1))])
二、不能放(再开辟一个缆车,所以 dpdpdp 转移时 dp[i]dp[i]dp[i] 要加 111):
dp[i∣(1<<(j−1))]=min(dp[i∣(1<<(j−1))],dp[i]+1);dp[i|(1<<(j-1))]=min(dp[i|(1<<(j-1))],dp[i]+1); dp[i∣(1<<(j−1))]=min(dp[i∣(1<<(j−1))],dp[i]+1);
c[i∣(1<<(j−1))]=max(w−a[j],c[i∣(1<<(j−1))]);c[i|(1<<(j-1))]=max(w-a[j],c[i|(1<<(j-1))]); c[i∣(1<<(j−1))]=max(w−a[j],c[i∣(1<<(j−1))]);
3. 初始条件:初始化缆车数:dp[0]=1,初始化缆车承重:c[0]=w;
4. 循环顺序:我们第一层循环 iii ,枚举状态,第二层循环 jjj,枚举当前状态下未上车的猫即可;
5. 输出dp[1<<n−1]dp[1<<n-1]dp[1<<n−1]。
这样代码就有了:
例题3: 最短哈密顿路径
这题是个经典的状压DP题(当然也较难)
这一题不同于我们上面的状压DP,并没有上面几题的限制条件,同时状态定义也不好想。我们先考虑状态定义:
> 状态 iii 用 111 表示该点走过,用 000 表示该点走过没走过。
那我们现在来考虑DP:
1. 状态:此处状态比较不好想,我们用dp[i][j]dp[i][j]dp[i][j]表示 iii 状态下走过的点中终点为 jjj 的最小距离;
2. 转移方程:利用FloydFloydFloyd的思想,当前点可以由上一个点过来,即:
dp[i][j]=dp[x][k]mindp[i][j]=dp[x][k]_{min} dp[i][j]=dp[x][k]min
其中 iii 表示当前状态,jjj 表示当前终点, xxx===i&(~(1<<(j-1)))(把第 jjj 位的标记改为没走过),表示上一个状态, kkk 表示上一个点;
3. 初始条件:标记起点:dp[1][0]=0;;
4. 循环顺序:我们第一层循环 iii ,枚举状态,第二层循环 jjj,枚举当前终点,第三层循环 kkk,枚举上一个点即可;
5. 显而易见,答案是 dp[1<<n−1][n]dp[1<<n-1][n]dp[1<<n−1][n];
最后放一下代码:
补充题:
毕业旅行问题
[NOIP2016 提高组] 愤怒的小鸟
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
NO.5 后记
大家看完后,你学废了吗?
请大佬们奉上一个赞吧!
最后,祝大家2024CSP复赛rp++!