状压DP总结
状压DP入门详解：从思路到实战
一、什么是状压DP？
状态压缩动态规划（简称状压DP）是一种利用二进制位运算来表示和处理状态的动态规划方法。它主要解决的是状态过多但规模较小的问题，通常适用于数据范围在 n ≤ 25 的情况。
为什么需要状压？
在传统的DP中，如果状态是某个集合，我们很难直接用一个数组维度来表示。而二进制恰好可以很自然地表示"选"或"不选"两种状态，多个二进制位组合就能表示一个集合。
二、状压DP的核心——位运算
必备的位运算操作
| 操作 | 代码 | 含义 |
|---|---|---|
| 判断第i位是否为1 | (j>>i)&1 |
检查状态j中第i个元素是否被选中 |
| 将第i位设为1 | S|=(1<<i) |
在状态j中选择第i个元素 |
| 检查相邻1 | j&(j>>1) |
检查状态j中是否有相邻的1 |
| 取交集 | S&T |
两个状态取交集 |
| 取并集 | 两个状态取并集 |
三、状压DP的通用解题框架
解题四步法：
-
状态设计
- 定义
dp[j] 或dp[i][j] ，其中j 是二进制状态 - 明确状态含义：
dp[j] 表示达到状态S的答案（方案数/最小代价等）
- 定义
-
状态转移
- 考虑如何从已知状态推导到未知状态
- 通常形式：
dp[新状态]=min/max(dp[新状态], dp[原状态]+代价) - 或者：
dp[新状态]+=dp[原状态]
-
初始化
- 确定起点状态的初始值
- 通常：
dp[0]=0 或dp[初始状态]=1
-
结果提取
- 从最终状态中提取答案
- 可能是
dp[全集] 、min(dp[所有状态]) 等
四、经典例题详解
例题1：P1879 Corn Fields G
题目大意：在
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[2005],mod=1e8,dp[25][1<<13];
signed main()
{
cin>>m>>n;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
int x;
cin>>x;
a[i]=(a[i]<<1)+x;
}
}
dp[0][0]=1;
for(int i=1;i<=m;i++)
{
for(int j=0;j<(1<<n);j++)
{
if((j&(j<<1))==0)
{
if((j&a[i])==j)
{
for(int k=0;k<(1<<n);k++)
{
if((j&k)==0)
{
dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;
}
}
}
}
}
}
int ans=0;
for(int i=0;i<(1<<n);i++)
ans=(ans+dp[m][i])%mod;
cout<<ans;
return 0;
} 关键点：
- 用
a[i] 存储每行的土地状态，1表示肥沃 - 预处理所有行内不相邻的状态
- 转移时检查：①状态与土地匹配 ②上下行不相邻
五、状压DP的常见题型总结
| 题型 | 特征 | 解题关键 |
|---|---|---|
| 棋盘放置 | 棋盘上有放置限制 | 预处理行内合法状态，检查行间兼容性 |
| 最短路径 | 需要访问所有点一次 | 状态表示已访问的点集，维度记录当前位置 |
| 集合划分 | 将集合划分成若干子集 | 状态表示已分配的元素集合 |
六、实战技巧与注意事项
1. 空间优化
- 当
n=20 时，状态数可达2^20≈1e6 ，要注意数组开不下时使用滚动数组
2. 时间优化
- 预处理合法状态和状态间关系
- 使用剪枝减少不必要的状态转移
3. 调试技巧
// 打印二进制状态（调试用）
void print(int s,int n) {
for(int i=n-1;i>=0;i--)
{
cout<<((s>>i)&1);
}
cout<<endl;
}4. 常见错误
- 位运算优先级问题：多用括号，如
(s >> i) & 1 - 数组越界：注意状态范围是
0到(1<<n)-1 - 初始化不完整：确保所有起点状态正确初始化
七、推荐练习顺序
- P1879 Corn Fields G - 最基础的棋盘状压DP
- P1171 售货员难题 - 经典的旅行商问题
- P1433 吃奶酪 - 二维平面上的最短路径