#创作计划#教你食用状压DP
2024-11-04 14:01:37
发布于：福建
在被Macw的排位赛#13第7题拿捏后，我不得不去烹调一波状压DP，现做出此文，教大家食用状压DP。
这是个好东西，学会了可以做好多绿题和蓝题
阅读此文前，你需要自学DP、进制数以及位运算的基本知识等。
好，进入正文！
No.1 前置知识
状压DP（状态压缩动态规划）是一种特殊的动态规划方法，它将状态压缩为二进制整数来表示，以便更有效地进行状态转移和优化。
好！看完后，我们知道，状压DP=状压（状态压缩）+DP（动态规划）；
DP就先不介绍了，接下来让我们先谈谈状态压缩。
No.2 状态压缩
状态压缩是一种将“物品”状态通过 进制数表示的技巧（ 为状态数, 一般较小，通常为 ）。通常用一个整数其 进制中的第 位上的数来表示第 个“物品”的状态，状态压缩的核心在于使用位运算来处理和比较。
比如：二进制可以用于表示棋盘上一行的格子是否有棋子（有无，共 种）、硬币的正反面（正反，共 种）、该物品取不取（是否取，共 种）等。
比如我们有一行 个方格，在方格里填充 和 ，那么总的方案数就应该有 个。我们现在使用状态压缩，将 个方格看成 位， 和 都看成二进制，那么这 位就组成了一个二进制数。比如0001 0010转成十进制就是 ，它表示从右往左第 和第 个方格里是 。
我们假设 为 ，考虑一个状态 ，这个 的二进制取值范围在0001~1111之间，二进制从右往左第 位为 表示取第 块水晶；
那么我们可以枚举 ~ 的区间，即枚举二进制0001~1111这个区间里的所有状态，然后求出状态 中取的水晶之和，最后判断质数即可。
#include<bits/stdc++.h>
using namespace std;
int n,a[20],ans;
int check(int x){//判断质数
if(x<=1) return 0;
for(int i=2;i*i<=x;i++){
if(x%i==0){
return 0;
}
}
return 1;
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=1;i<(1<<n);i++){//枚举所有状态 1<<n -> 2^n
int sum=0;
for(int j=0;j<n;j++){
if(i&(1<<j)){//判断第j位是否为1
sum+=a[j];//求和
}
}
if(check(sum)) ans++;//如果为质数，答案加1
}
cout<<ans;
return 0;
}
和上题差不多，我们输入时可以用一个 存储会产生冲突的披萨，仍然枚举所有状态，判断一个状态中会不会产生冲突，否则答案加 ，具体看代码
#include<bits/stdc++.h>
using namespace std;
int n,m,a[20],ans;
vector<int>e[20];//e[i]存储会和i号披萨冲突的披萨
int main(){
cin>>n>>m;
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
e[a-1].push_back(b-1);//存储冲突，下标减一是为了下面的判断
e[b-1].push_back(a-1);
}
for(int i=0;i<(1<<n);i++){//枚举状态
int f=0;//f=1 状态i不成立;f=0 状态i成立
for(int j=0;j<n;j++){
if(i&(1<<j)){//判断是否选了j号披萨
for(int k=0;k<e[j].size();k++){
if(i&(1<<(e[j][k]))){//判断和j号披萨冲突的披萨有没有选
f=1;
break;
}
}
if(f) break;
}
}
if(!f) ans++;//如果状态是成立的，答案加1
}
cout<<ans;
return 0;
}
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让 的后 位移到前面去，原来的前 位会溢出；
我们可以用x>>16让 的前 位移到后面去，原来的后 位会溢出；
两个相加即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
unsigned int n;//32位整数才可以满足（满足让16位溢出，一共只有32位，int和long long不行）
int main(){
cin>>n;
cout<<(n<<16)+(n>>16);//两个相加完成高低位交换
return 0;
}
No.4 状压DP
接下来我们回到状压DP。
状压DP：顾名思义，就是用状态压缩实现DP；
状压DP主要分为棋盘式和集合式：
- 棋盘式：主要用于处理棋盘类问题，通过状态压缩来表示棋盘上每个格子的状态（如是否有障碍物、是否被占用等）。这种方法常用于解决如迷宫问题、棋盘游戏等问题；
- 集合式：用于表示一个集合中的元素是否被选择。这种方法适用于处理如背包问题、选择问题等，通过二进制数来表示集合中的元素状态，每个二进制位对应集合中的一个元素，1表示选择该元素，0表示不选择。
4.1 棋盘式：
例题1：[SCOI2005] 互不侵犯
首先，我们根据之前的经验，考虑枚举一行的所有状态，即从 ~ 枚举一遍，判断合法的状态，用一个数组存下来，并存储 状态中放的国王数量；
那，怎么判断合法呢？怎么算放的国王数量呢？这就要用到上文说的一些技巧了：
//算放的国王数量
ll check(int x){//统计一个数二进制中一的个数
ll sum=0;
while(x){
sum++;//每消去一个1，sum++
x&=(x-1);//上表中的：消去二进制中最右侧的1
}
return sum;
}
//--------------------------
//当前行状态i ，上一行状态j
//判断上下行合法 ：
// i&j ->为1：两行中有位置都放了国王（不成立）
//例：
//j：01001
//i：01010
//i&j:01000 当前状态中从右往左第4个位置上下行都有国王
//判断当前行合法 ：
// i&(j<<1) ->为1：当前行中有些国王右上角也有国王（不成立）
//例：
//j：01100
//j<<1：11000
//i：10010
//i&(j<<1):10000 当前状态中从右往左第5个国王的右上角也有个国王
// i&(j>>1) ->为1：当前行中有些国王左上角也有国王（不成立）
//例：
//j：01100
//j>>1：00110
//i：10010
//i&(j<<1):00010 当前状态中从右往左第2个国王的左上角也有个国王
//i&(i<<1) ->为1：当前行中有些国王旁边也有国王（不成立）
//例：
//i：01101
//i<<1：11010
//i&(i<<1)：01000 当前状态中从右往左第4个国王的右边也有个国王
这样就可以预处理所有的状态了：
for(int i=0;i<(1<<n);i++){//枚举所有状态
if(i&(i<<1)) continue;//不合法则跳过
f[++L]=i;//保存合法的状态
cnt[L]=check(i);//记录每个状态放的国王数量（check函数见上文） L 表示合法的状态总数
dp[1][L][cnt[L]]=1;//dp数组初始化（详见下文）
}
接下来，我们考虑DP：
- 状态：表示第 行状态为 ，当前共放了 个国王的方案数；
- 转移方程：由于当前状态可以由上一行所有不会产生冲突的状态转移而来，所以状态转移方程为
其中， 表示当前第 行， 表示当前状态， 表示上一状态， 表示当前放的国王总数， 和 数组见上文；
3. 初始条件：由于 数组需要由上一行得到，所以我们需要初始化 数组的第一行，而 数组第一行的方案即所有合法的状态，所以在枚举合法方案时初始化即可，dp[1][L][cnt[L]]=1;；
4. 循环顺序：我们第一层循环 ，表示第 层，第二层循环 ，枚举当前状态，第三层循环 ，枚举上一行状态，如果状态 和状态 不会产生冲突，那么循环 ，从 （至少有当前状态放的国王数量）到 （数量上限），枚举当前放的国王总数；
5. 显而易见，答案是 数组中第 行放 个国王的所有状态的方案之和，即
那么DP自然就出来了
for(int i=2;i<=n;i++){//从第2行开始
for(int j=1;j<=L;j++){//枚举当前行所有状态
for(int l=1;l<=L;l++){//枚举上一行所有状态
if(f[j]&f[l]||f[j]&(f[l]<<1)||f[j]&(f[l]>>1)) continue;//两行会冲突则跳过
for(int g=cnt[j];g<=k;g++){//枚举国王数
dp[i][j][g]+=dp[i-1][l][g-cnt[j]];//状态转移方程
}
}
}
}
最后贴一波代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
ll n,k,dp[15][2005][105],cnt[2005],f[2005],L;
ll check(int x){//求一个状态的国王数
ll sum=0;
while(x){
sum++;
x&=(x-1);
}
return sum;
}
int main(){
cin>>n>>k;
for(int i=0;i<(1<<n);i++){//枚举所有状态
if(i&(i<<1)) continue;
f[++L]=i;
cnt[L]=check(i);
dp[1][L][cnt[L]]=1;//初始化
}
for(int i=2;i<=n;i++){//DP过程
for(int j=1;j<=L;j++){
for(int l=1;l<=L;l++){
if(f[j]&f[l]||f[j]&(f[l]<<1)||f[j]&(f[l]>>1)) continue;
for(int g=cnt[j];g<=k;g++){
dp[i][j][g]+=dp[i-1][l][g-cnt[j]];//状态转移方程
}
}
}
}
ll ans=0;
for(int i=1;i<=L;i++){//答案
ans+=dp[n][i][k];
}
cout<<ans;
return 0;
}
例题2：
[USACO06NOV] Corn Fields G
Acwing.玉米田
乌龟养殖场
额，好好好，这么玩是吧（我赛时咋没发现），这几题差不多（差别在有的可以一个都不放），所以这里具体就讲这题。
这一题和上一题差不多，但少了个数限制，且冲突条件变了。
所以我们先来想想如何存图。这一题里，图显然只会在判断第 行状态是否有在不适合种草地方种草，怎么判断呢？如果把牧场第 行的土地状况存储为一个状态 ，当前状态为 ，我们可以用(~mp[i])&j来判断。为什么？~mp[i]会把第 行不适合种草的地方标记为 ，肥沃的反标记为 ，而(~mp[i])&j有值则说明~mp[i]中有些 的位置状态 中也为 ，即在不适合种草的地方种了草，所以不成立。那既然会用到~mp[i]，那么我们输入时就可以把 数组取反，这样就不用后面取反了。
那这样就可以存图了：
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int x;
cin>>x;//读入地图
mp[i]=(mp[i]<<1)+!x;//取反存储
}
}
接下来为了存储所有合法状态，我们来想想怎样判断状态合法。
有了上题的经验，当前状态若为 ，那么i&(i<<1)有值则说明当前状态中有连续的 ，即有些种草的地旁边也有草，不成立；
上行状态为 ，若i&j有值则说明两行中有位置都是 ，即都种了草，不成立。
存储所有合法状态时用i&(i<<1)判断就可以了：
for(int i=0;i<(1<<m);i++){//枚举所有状态，因为都不放也可以，所有从0开始
if(i&(i<<1)) continue;//不成立跳过
zt[++L]=i;////保存合法的状态 L 表示合法的状态总数
}
我们接下来再考虑DP：
- 状态：表示第 行状态为 的方案数；
- 转移方程：由于当前状态可以由上一行所有不会产生冲突的状态转移而来，所以状态转移方程为
其中， 表示当前第 行， 表示当前状态， 表示上一状态；
3. 初始条件：由于 数组需要由上一行得到，所以我们也可以初始化第0行放一个的情况：dp[0][1]=1;；
4. 循环顺序：我们第一层循环 ，表示第 层，第二层循环 ，枚举当前状态，第三层循环 ，枚举上一行状态即可；
5. 显而易见，答案是 数组中第 行放 个国王的所有状态的方案之和，即
最后放一下代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const ll P=1e8;
int n,m,mp[15],zt[1<<12],L,dp[15][1<<12]; //mp 把地图反过来存 zt 存储所有状态
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int x;
cin>>x;
mp[i]=(mp[i]<<1)+!x;//取反存储
}
}
for(int i=0;i<(1<<m);i++){
if(i&(i<<1)) continue;//相邻的有种草
zt[++L]=i;//存储状态
}
dp[0][1]=1;//初始化
for(int i=1;i<=n;i++){//枚举当前行
for(int j=1;j<=L;j++){//枚举当前状态
if(zt[j]&mp[i]) continue;//会与地图产生冲突则跳过
for(int k=1;k<=L;k++){//枚举上行状态
if(zt[j]&zt[k]||zt[k]&mp[i-1]) continue;//两行冲突或上行与上行地图会产生冲突则跳过
dp[i][j]=(dp[i][j]+dp[i-1][k])%P;//状态转移
}
}
}
ll ans=0;
for(int i=1;i<=L;i++) ans=(ans+dp[n][i])%P;//求答案
cout<<ans;
return 0;
}
例题3：骨牌铺法/蒙德里安的梦想
和前面不同，我们考虑按列放置（即状态表示竖列）。
对于一个状态，我们把 记为竖放， 记为横放；
那么，一个状态中若有连续的 的个数为奇数，则不成立（因为 为竖放，而竖放一块骨牌会占 格，若连续 的的数量为奇数，说明有半块骨牌），所以我们可以筛选所有合法的状态：
for(int i=0;i<(1<<n);i++){//枚举状态
state[i]=1;//state标记状态i是否合法
int cnt=0;//cnt统计连续0的数量
for(int j=0;j<n;j++){//枚举所有骨牌
if(i>>j&1){//如果是1
if(cnt&1){//如果连续0的个数是奇数个
state[i]=0; //状态不成立
}
cnt=0;//否则清0继续统计
}else{//是0
++cnt;//统计连续0的个数
}
}
if(cnt&1) state[i]=0;//特判最后一段
}
那么我们接下来考虑DP：
- 状态：表示第 列状态为 的方案数；
- 转移方程：由于当前状态可以由上一列所有不会产生冲突的状态转移而来，
那怎么判断合法呢？首先，把两列合并，上列横放（），当前列必为空（）；上列竖放，这列为竖放或横放（或），所以，两行合并合法，则(j&k)==0；其次，如上述，j|k为必定是两列有一个横放，为则必定是两列都竖放，我们上面预处理过，连续的 的个数不为奇数则成立，即state[j|k]。
所以状态转移方程为
其中， 表示当前第 列， 表示当前状态， 表示上一列状态；
3. 初始条件：我们可以初始化第0列一个也不放的情况：dp[0][0]=1;；
4. 循环顺序：我们第一层循环 ，表示第 列，第二层循环 ，枚举当前状态，第三层循环 ，枚举上一列状态即可；
5. 由于数组最后一列无法横放，所有答案是 。
最后放一下代码：
#include<bits/stdc++.h>
using namespace std;
const int max_n=15,max_m=(1<<15)+5;
int n,m,state[max_m];
long long dp[max_n][max_m];//dp开long long
int main(){
cin>>n>>m;
for(int i=0;i<(1<<n);i++){//预处理
state[i]=1;
int cnt=0;
for(int j=0;j<n;j++){
if(i>>j&1){
if(cnt&1){
state[i]=0;
}
cnt=0;
}else{
++cnt;
}
}
if(cnt&1) state[i]=0;
}
dp[0][0]=1;//初始化
for(int i=1;i<=m;i++){//枚举列
for(int j=0;j<(1<<n);j++){//枚举当前列状态
for(int k=0;k<(1<<n);k++){//枚举上列状态
if((j&k)==0&&state[j|k]){//合法
dp[i][j]=dp[i][j]+dp[i-1][k];//转移
}
}
}
}
cout<<dp[m][0];//输出
return 0;
}
补充题：
[NOI2001] 炮兵阵地
剑之试炼
4.2 集合式：
对于每一包糖，我们可以用a[i]|=(1<<(w-1))把第 包糖压缩为一个状态，便于我们完成“吃糖”的操作，所以：
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
int w;
cin>>w;
a[i]|=(1<<(w-1));//把每包糖压缩为一个状态（把a[i]的第(w-1)位记为1）
}
dp[a[i]]=1;//初始化（见下文）
}
接下来考虑DP:
-
状态：我们用表示 状态下选的最少的糖包数；
-
转移方程： 状态下选择第 包糖的方案可以由当前状态转移，即：
其中i|a[j]表示 状态下选择第 包糖后的状态，表示当前又选了一包糖；
-
初始条件：初始化每一包糖：
dp[a[i]]=1;，什么也不放：dp[0]=1； -
循环顺序：我们第一层循环 ，枚举状态，第二层循环 ，枚举当前糖果即可；
-
如果没有更改，则说明无法凑齐 包糖，输出 ；否则输出。
最后放个代码：
#include<bits/stdc++.h>
using namespace std;
const int maxx=1<<20;
int n,m,k,ans=1e9;
int a[105],dp[maxx];
int main(){
memset(dp,0x3f,sizeof(dp));//赋为较大值
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
int w;
cin>>w;
a[i]|=(1<<(w-1));//存储糖果
}
dp[a[i]]=1;//初始化
}
dp[0]=0;//初始化
for(int i=1;i<(1<<m);i++){//枚举m颗糖果的状态
for(int j=1;j<=n;j++){//枚举糖果
dp[i|a[j]]=min(dp[i|a[j]],dp[i]+1);//转移
}
}
cout<<(dp[(1<<m)-1]==0x3f3f3f3f? -1: dp[(1<<m)-1]);//输出
return 0;
}
例题2：小猫爬山
[USACO12MAR]Cows in a Skyscraper G
两题一样（都也可以用记搜做），这里讲小猫爬山。
此题有两个因素：当前缆车剩余承重与缆车数，所有我们分别用两个数组记录；
接着考虑装态：状态 ， 表示猫已上缆车， 表示未上缆车；
最后考虑DP：‘
-
状态：我们用表示 状态下使用的最少的缆车数，用表示 状态下所有的缆车中最大的剩余承重（贪心）；
-
转移方程：
i|[a[j]表示该猫上缆车后的状态，然后由当前状态转移最小值（更小的缆车数量），由当前转移最大值（更大的剩余承重）分两种情况 ：
一、能放 ：
二、不能放（再开辟一个缆车，所以 转移时 要加 ）:
-
初始条件：初始化缆车数：
dp[0]=1，初始化缆车承重：c[0]=w； -
循环顺序：我们第一层循环 ，枚举状态，第二层循环 ，枚举当前状态下未上车的猫即可；
-
输出。
这样代码就有了：
#include<bits/stdc++.h>
using namespace std;
int n,w,a[20],dp[1<<18],c[1<<18];
int main(){
cin>>n>>w;
memset(dp,0x3f,sizeof(dp));//赋为较大值
for(int i=1;i<=n;i++){
cin>>a[i];
}
dp[0]=1,c[0]=w; //初始化
for(int i=0;i<(1<<n);i++){//枚举状态
for(int j=1;j<=n;j++){//枚举猫
if(i&(1<<(j-1))) continue;//上车了跳过
if(c[i]>=a[j]){//能装下
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))]);//转移
}else{//装不下，再开一个缆车
dp[i|(1<<(j-1))]=min(dp[i|(1<<(j-1))],dp[i]+1);//转移 +1再开一个缆车
c[i|(1<<(j-1))]=max(w-a[j],c[i|(1<<(j-1))]);//状压 w-a[j]新开的缆车承重为w
}
}
}
cout<<dp[(1<<n)-1];//输出
return 0;
}
例题3: 最短哈密顿路径
这题是个经典的状压DP题（当然也较难）
这一题不同于我们上面的状压DP，并没有上面几题的限制条件，同时状态定义也不好想。我们先考虑状态定义：
状态 用 表示该点走过，用 表示该点走过没走过。
那我们现在来考虑DP：
-
状态：此处状态比较不好想，我们用表示 状态下走过的点中终点为 的最小距离；
-
转移方程：利用的思想，当前点可以由上一个点过来，即：
其中 表示当前状态， 表示当前终点， i&(~(1<<(j-1)))（把第 位的标记改为没走过），表示上一个状态， 表示上一个点；
-
初始条件：标记起点：
dp[1][0]=0;； -
循环顺序：我们第一层循环 ，枚举状态，第二层循环 ，枚举当前终点，第三层循环 ，枚举上一个点即可；
-
显而易见，答案是 ；
最后放一下代码：
#include<bits/stdc++.h>
using namespace std;
const int maxx=(1<<20)+5;
int n;
int mp[25][25],dp[maxx][25];
int main(){
cin>>n;
memset(dp,0x3f,sizeof(dp));//初始化为较大值
for(int i=0;i<n;i++){//下标从0开始，方便左移
for(int j=0;j<n;j++){
cin>>mp[i][j];
}
}
dp[1][0]=0;//初始化
for(int i=1;i<(1<<n);i++){//枚举状态
for(int j=0;j<n;j++){//枚举终点
if(i>>j&1){//可以作为终点
for(int k=0;k<n;k++){//就枚举上一点
if(j==k) continue;//重复跳过
if(i>>k&1){//上一点成立
dp[i][j]=min(dp[i][j],dp[i&(~(1<<j))][k]+mp[k][j]);//走过来
}
}
}
}
}
cout<<dp[(1<<n)-1][n-1];//答案
return 0;
}
补充题：
毕业旅行问题
[NOIP2016 提高组] 愤怒的小鸟
No.5 后记
大家看完后，你学废了吗？
请大佬们奉上一个赞吧！
最后，祝大家2024CSP复赛rp++！
int f(){ rp--; return f()}
有帮助，赞一个