#创作计划# 位运算和状态压缩动态规划
2026-05-16 16:16:06
发布于:广东
前言
依旧学啥写啥,话说现在不实名还能发吗?
施工ing
正文
前言-位运算
此处只解析状压DP可能使用的位运算。
运算符
需要注意的是,除取反外的位运算符优先级低于算术运算符,而按位于,按位或,异或优先级低于比较运算符。[1]
移位:a << b左移或a >> b右移
将二进制a移位b位。(详细的移位内容详见运算 - OI Wiki - 位运算符)
如:
int a = 22;//10110
int b = a<<2;
int c = a>>2;
cout << b << ' ' << c;// 88 5 (1011000 101)
注意到左移时低位用0填充,移位溢出位舍去。
按位运算符 & |
按位与& 和按位或 | 接收两个操作数,并对其按每一位进行与/或操作。
int a=6,b=10;//0110 1010
cout << (a|b) << ' ' << (a&b);//14 2(1110 0010)
什么是状态压缩动态规划
状压 DP 是动态规划的一种,通过将状态集合转化为整数记录在 DP 状态中来实现状态转移的目的.
为了达到更低的时间复杂度,通常需要寻找更低状态数的状态.大部分题目中会利用二元状态,用位二进制数表示个独立二元状态的情况.
——OI Wiki[2]
通俗来讲,状压DP通过使用二进制表示状态。
例题
P3052 [USACO12MAR] Cows in a Skyscraper G / A90642.Cows in a Skyscraper G
想法
注意到对于每一头牛都有放了/没放两种状态,可以使用二进制表示。我们考虑状压DP。
据此设计出状态:
dp[i]表示对于二进制状态i最少使用的电梯数量。
显然当时不使用任何电梯,然而我们必须“留”一辆电梯让后续的状态可以转移,所以我们令初始状态为:
dp[0]=1,即没有牛上电梯的时候使用1辆电梯。
同时,最终答案的i是:
1111..<一共n个1>..111,表示头牛全部坐电梯下楼。
那么要获取这个值,我们发现这个值的值等于100000..<n个0>..000,刚好是1<<n的值。
因此,最终答案是:
dp[(1<<n)-1],也就是当所有牛全部坐了电梯。
啊对,还要新建一个数组存储当前电梯的已载重。
然后对于转移,考虑从当前状态为基础,减去一头牛。
那么就要枚举减去的这头牛i。
首先,如果当前状态没有这头牛,那么跳过。
然后,创建一个转移到当前状态的前向状态,赋值为从当前状态减去一个第i位是1,其他为0的数,也就是把这位设置成0。
更新有两种可能:
- 前向状态的使用电梯数量小于当前电梯数量,更新。
对于这个状态,如果前向的电梯载重加上当前牛的重量大于最大载重,那么要新一台电梯。 - 前向状态电梯数量等于当前且不需要新的电梯,更新。
更多细节见代码。
AC Code
#include<bits/stdc++.h>
using namespace std;
int n,w;
int c[20];
int lw[262144];//上一堂电梯的载重
#define gbit(i) (1<<(i-1))
int dp[262144];//已经使用电梯数量(包含当前没下去的)
int main(){
cin >> n >> w;
for(int i = 1;i <= n;i++){
cin >> c[i];
}
memset(dp,0x3f,sizeof dp);
memset(lw,0x3f,sizeof lw);
dp[0]=1;
lw[0]=0;//我们假设0头牛的时候有一台载重0的电梯
for(int m = 1;m <= (1<<n)-1;m++){
for(int i = 1;i <= n;i++){//从没有牛i的情况转移来
if(!(m&gbit(i))) continue;//当前状态没有牛i
int pm = m-gbit(i);//获取没有牛i的状态
if(dp[pm]<dp[m]){//趟数少,优
dp[m]=dp[pm];
int tmp = lw[pm]+c[i];//当前载重
if(tmp>w){//叫新的
dp[m]++;
lw[m]=c[i];
}else{
lw[m]=tmp;
}
}
if(dp[pm]==dp[m]){
int tmp = lw[pm]+c[i];
if(tmp>w) continue;//对于当前状态,趟数大于已有的,不好。
if(tmp<lw[m]){//当前最后载重更优
lw[m]=tmp;
}
}
}
}
cout << dp[(1<<n)-1];
}
引用
位运算操作符:https://oi-wiki.org/lang/op/#位操作符
位操作:https://oi-wiki.org/math/bit
全部评论 2
注意到没有讲解状压dp的核心,这是因为我没时间了。
昨天 来自 广东
0要是我国的水稻有这么高产就好了
昨天 来自 浙江
0啥意思?
昨天 来自 上海
0看贴主的产量
昨天 来自 浙江
0


















有帮助,赞一个