#创作计划#教你食用状压DP
2024-10-21 18:47:19
发布于:福建
在被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()}
全部评论 10
顶
昨天 来自 美国
2顶!
16小时前 来自 福建
1顶
昨天 来自 广东
1顶!
7小时前 来自 福建
0顶
9小时前 来自 浙江
0顶
9小时前 来自 四川
0顶
10小时前 来自 江苏
0顶!
11小时前 来自 福建
0顶!
昨天 来自 福建
0顶!
昨天 来自 福建
0
有帮助,赞一个