状态压缩 DP

当动态规划的约束条件涉及“一个集合内的元素选取状态”，且集合规模较小（通常 $N$ 小于或等于 20）时，多维数组已无法有效表达复杂的状态组合。此时，需要利用计算机底层的二进制机制，将一个集合的选取状态精确压缩为一个十进制整数，以此实现降维。

一、状态压缩的核心原理与位运算基础

1. 集合的二进制映射

假设有一个包含 5 个元素的集合，我们选取了编号 0、2、3 的元素。这一状态可以表示为二进制串 01101（约定从右向左按 $0 \sim 4$ 编号）。

这个二进制状态对应的十进制整数为 $13$。通过这种映射，我们用一个整数就能唯一标识一个子集的状态。

2. 状态转移中的位运算

在状态压缩 DP 中，所有关于集合的交、并、查操作，均需转化为位运算以保证 $O(1)$ 的执行效率：

• 状态查询：判断整数 $S$ 的第 $i$ 位是否为 1，表达式为 (S >> i) & 1。
• 状态添加：将整数 $S$ 的第 $i$ 位强制置为 1，表达式为 S | (1 << i)。
• 状态剥离：在已知第 $i$ 位为 1 的前提下，将其置为 0，表达式为 S ^ (1 << i)。
• 相邻冲突校验：判断状态 $S$ 内部是否存在相邻的 1，表达式为 S & (S << 1)。若运算结果不为 0，说明存在相邻元素，该状态不合法。

二、核心模型一：逐行网格放置与地形掩码

场景特征：在一个 $N \times M$ 的网格上放置物品，要求相邻位置不能同时放置，且部分网格损坏不可用。

推导过程：

网格的放置状态是按行递推的，第 $i$ 行的合法放置方案仅受第 $i-1$ 行约束。

定义 $dp[i][S]$ 表示处理至第 $i$ 行，且第 $i$ 行的放置状态为 $S$ 时的总方案数。

为了处理不可用的网格，引入地形掩码 (Map Mask) 技巧。将输入的每一行地形也压缩为一个整数 $a[i]$（可用为 1，损坏为 0）。在枚举状态 $S$ 时，利用 (S & a[i]) == S 即可快速校验放置位置是否全在可用网格上。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=15,M=1<<13;
const int mod=1e8;
int dp[N][M]; 
int a[N]; 
int state[M],tot;

// 预处理单行内无相邻元素的合法状态
void init(int m){
	for(int i=0;i<(1<<m);i++){
		if(!(i&(i<<1))) state[++tot]=i;
	}
}

void solve(){
	int n,m;
	cin>>n>>m;
	init(m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int x;
			cin>>x;
			a[i]=(a[i]<<1)|x; // 压缩地形为整数
		}
	}
	
	dp[0][0]=1; 
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=tot;j++){ 
			int s1=state[j];
			if((s1&a[i])!=s1) continue; // 地形掩码校验
			
			for(int k=1;k<=tot;k++){ 
				int s2=state[k];
				if(s1&s2) continue; // 跨行相邻冲突校验
				
				dp[i][s1]=(dp[i][s1]+dp[i-1][s2])%mod;
			}
		}
	}
	
	int ans=0;
	for(int i=1;i<=tot;i++) ans=(ans+dp[n][state[i]])%mod;
	cout<<ans<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

三、核心模型二：TSP 与路径集合压缩

场景特征：求解经过给定节点集合的最短路径或全排列问题。此类问题若记录确切的访问顺序，复杂度将达到 $O(N!)$。

推导过程：

路径规划的核心在于“已经访问了哪些节点”以及“当前处于哪个节点”，中间的跳转顺序对后续决策无影响。

定义 $dp[S][i]$ 表示已访问的节点集合状态为 $S$，且最后停留在节点 $i$ 时的最短路径。

状态转移：枚举状态 $S$ 中存在的节点 $i$，再枚举走到 $i$ 的前驱节点 $j$（$j$ 也必须在集合 $S$ 中）。

下面实现的是从 1 出发、走完所有点后回到 1 的最短回路，支持 $n\le20$。如果题目不用返回起点，结尾就不要再加 dist[i][1]。这张 long long 表约占 168 MiB，使用前看清内存限制；只跳过部分状态并不会缩小已经声明的数组。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=21,M=1<<20;
int dist[N][N];
int dp[M][N];

void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++) cin>>dist[i][j];
	}
	
	memset(dp,0x3f,sizeof dp);
	if(n==1){ cout<<0<<'\n'; return; }
	dp[1][1]=0; 
	
	int max_state=1<<n;
	for(int s=1;s<max_state;s++){
		for(int i=1;i<=n;i++){
			if(!((s>>(i-1))&1)) continue; 
			
			int pre_s=s^(1<<(i-1)); // 状态剥离
			for(int j=1;j<=n;j++){
				if(!((pre_s>>(j-1))&1)) continue; 
				dp[s][i]=min(dp[s][i],dp[pre_s][j]+dist[j][i]);
			}
		}
	}
	
	int ans=1e18;
	for(int i=2;i<=n;i++){
		ans=min(ans,dp[max_state-1][i]+dist[i][1]);
	}
	cout<<ans<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

四、集合划分的基石：子集枚举与 $O(3^n)$ 的来历

场景特征：在某些问题中，我们不是每次只加入一个节点，而是需要把若干个元素打包成一个整体加入。比如我们要将一个集合 $S$ 拆分成多个互不相交的子集，这就需要枚举 $S$ 的所有内部子集。

1. 如何高效枚举子集？

假设当前状态为 $S = 1010_2$（即十进制 10，包含了第 1 位和第 3 位）。它的非空子集有 $1010_2, 1000_2, 0010_2$。

最暴力的做法是：从 $0$ 枚举到 $S$，逐个用 (sub & S) == sub 检查。但这会跑过大量根本不在 $S$ 里的无效数字，效率极低。

核心技巧：通过 sub = (sub - 1) & S，我们可以直接在 $S$ 的子集内部连续“跳跃”。

// 依赖变量：S 为当前要枚举子集的集合，例如 S = 10
// 这段逻辑直接嵌套在你的状态枚举循环内
for (int sub = S; sub; sub = (sub - 1) & S) {
    // sub 必然是 S 的非空子集
    int remain = S ^ sub; // 从 S 中剔除 sub 剩下的那部分
    
    // 状态转移示例：
    // dp[S] = min(dp[S], dp[remain] + cost[sub]);
}

物理推导：以 $S = 1010_2$ 为例，假设当前 $sub = 1000_2$。我们想找下一个更小的子集。正常的减一会得到 $0111_2$，但这多出了第 0 位和第 2 位。把 $0111_2$ 再与 $S$（$1010_2$）做一次按位与运算：0111 & 1010 = 0010。 看，那些不属于 $S$ 的 1 被“按位与”这道防线无情地过滤掉了，我们直接跳到了下一个合法的子集 $0010_2$！

2. $O(3^n)$ 复杂度是怎么来的？

如果外层循环枚举所有的 $S$（共 $2^n$ 种），内层再枚举 $S$ 的子集，总循环次数是多少？并不是 $O(4^n)$。对于一个有 $k$ 个元素的集合，它的子集有 $2^k$ 个。而在 $n$ 个元素的总集中，大小为 $k$ 的集合共有 $\binom{n}{k}$ 个。

根据二项式定理：

因此，这类子集枚举 DP 的时间复杂度是严谨的 $O(3^n)$。对于 $N \le 15$ 的数据规模，$3^{15} \approx 1.43 \times 10^7$，在 1 秒内跑完绰绰有余。

五、连通性与分组：集合划分 DP 与最小未选元素去重

场景特征：将 $N$ 个元素划分为若干个不相交的非空子集，且分组的顺序不影响最终结果。例如：给 $N$ 个人分组，每组有一个给定的成团成本 $w[sub]$，求最小总成本。

暴力转移的痛点： 如果我们直接套用前面的子集枚举：

去重解法：钉死一个元素 为了消除顺序带来的影响，我们可以立下一个规矩：当前这步切分出来的子集 sub，必须包含当前集合 S 中编号最小的那个元素！

不管你最终怎么分组，那个最小的元素总得归属在某个组里。我们就直接把包含它的那个组整个抠出来，这就彻底断绝了“先拿 A 后拿 B”和“先拿 B 后拿 A”的重复路径。

// 依赖数组：dp 为最小成本，w 为某个子集的单独成本，n 为元素总数
// 初始化：dp 数组全部赋为正无穷大，起步状态 dp[0] = 0

for (int S = 1; S < (1 << n); S++) {
    // 找到集合 S 中编号最小的元素（利用 lowbit 思想）
    // S & -S 能直接提取出最低位的 1 代表的值
    int p = S & -S; 
    
    // 只枚举包含了元素 p 的子集
    for (int sub = S; sub; sub = (sub - 1) & S) {
        if (sub & p) { // 核心：当前划分出的组必须包含这个最小元素
            int remain = S ^ sub;
            dp[S] = min(dp[S], dp[remain] + w[sub]);
        }
    }
}

六、高维前缀和（SOS DP）与子集转移（选学）

先修要求：熟练掌握多维前缀和的思想与基本位运算，对维度拓展有一定直觉。

场景特征：给定一个大小为 $2^N$ 的数组 $A$，需要求出一个新数组 $F$，满足 $F[S] = \sum_{sub \subseteq S} A[sub]$。 这类问题被称作 Sum Over Subsets (SOS) DP。

暴力解法的瓶颈： 如果对每一个 $S$ 都用前面的子集枚举算法去累加，总复杂度是 $O(3^N)$。当 $N=20$ 时，$3^{20} \approx 3.48 \times 10^9$，必然超时。我们迫切需要一种把复杂度降到 $O(N \cdot 2^N)$ 的方法。

物理推导：把子集看作高维空间 一维数组求前缀和是怎么做的？$S[i] = S[i-1] + A[i]$。 二维矩阵呢？先对每一行求一维前缀和，再对每一列求一维前缀和。 对于 $N$ 位的二进制数，我们可以把它看作一个 $N$ 维的超立方体，每一维只有 0 和 1 两个坐标。求所有的子集和，本质上就是在这个 $N$ 维空间里做一次高维前缀和！

• 第一步：只允许改变第 0 位（从 0 变成 1），把此时能累加的加起来。
• 第二步：只允许改变第 1 位（从 0 变成 1），把此时能累加的加起来。
• ……
• 第 $N$ 步：处理最后一位。

通过这种“一层层剥开”的维度转移，每一层只需扫描所有状态一次。

手推小例子：$N=2$。初始值 $F = A$。

• 处理第 0 位：对于第 0 位是 1 的状态，加上把它变成 0 的状态。 $F[01_2] += F[00_2]$ $F[11_2] += F[10_2]$
• 处理第 1 位：对于第 1 位是 1 的状态，加上把它变成 0 的状态。 $F[10_2] += F[00_2]$ $F[11_2] += F[01_2]$

仔细看最后的 $F[11_2]$，它不仅加上了初始的 $A[10_2]$（在第一步没动），还加上了更新后的 $F[01_2]$（包含了 $A[01_2]$ 和 $A[00_2]$）。完美汇总了四个子集！

下面是独立可运行的 SOS DP 核心验证程序：

// 功能：给定长度为 2^n 的数组 A，计算每个状态的子集和 F。
// 输入：第一行一个整数 n (1 <= n <= 20)。
//       第二行 2^n 个整数，代表 A[0] 到 A[2^n - 1]。
// 输出：一行 2^n 个整数，代表 F[0] 到 F[2^n - 1]。
/* 
样例输入：
2
1 2 3 4
样例输出：
1 3 4 10
*/
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 20;
int A[1 << N];
int F[1 << N];

void solve() {
    int n;
    if (!(cin >> n)) return;
    
    int max_state = 1 << n;
    for (int i = 0; i < max_state; i++) {
        cin >> A[i];
        F[i] = A[i]; // 初始状态，高维前缀和的起点
    }
    
    // 核心循环：逐个维度（位）进行前缀和累加
    for (int i = 0; i < n; i++) {
        for (int mask = 0; mask < max_state; mask++) {
            // 如果当前状态的第 i 位是 1，说明它可以被第 i 位为 0 的子集贡献
            if ((mask >> i) & 1) {
                // mask ^ (1 << i) 即把第 i 位的 1 拨成 0
                F[mask] += F[mask ^ (1 << i)];
            }
        }
    }
    
    for (int i = 0; i < max_state; i++) {
        cout << F[i] << (i == max_state - 1 ? "" : " ");
    }
    cout << '\n';
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
    return 0;
}

七、降维扩展：折半搜索 (Meet-in-the-Middle)（选学）

场景特征：当状态压缩的规模扩张至 $N \approx 40$ 时，$O(2^N)$ 的时空开销将导致常规状压 DP 失效。

折半搜索的独立枚举与两半配对，详见《分治与折半搜索》；这里用点灯问题体会位掩码怎样表示互补状态。

推导过程：

将整个搜索空间一分为二。

前提是两半能独立枚举，并且能高效找到互补状态。不是看到 $N\approx40$ 就能把任意 DP 拦腰切开。

1. 对前 $N/2$ 个元素进行穷举搜索，将达成的状态及其最优代价存入哈希表或排序数组。

2. 对后 $N/2$ 个元素进行穷举搜索。在每次搜索到终点时，计算出需要的“互补状态”，并前往第一阶段建立的哈希表中查询。

   此方案可将时间复杂度由 $O(2^N)$ 降维至 $O(2^{N/2} \cdot \log(2^{N/2}))$。

下面的代码具体在解什么？——点灯问题（P2962）

有 $n$ 盏初始全部熄灭的灯，按下第 $u$ 个开关，会同时翻转灯 $u$ 以及所有与它直接相连的灯。求把灯全部点亮的最少操作次数。输入第一行是 n m，接下来 m 行每行给一条无向边 u v，灯的编号为 1..n。

按同一个开关两次就抵消了，所以每个开关只考虑按或不按。adj[u] 记录它会翻转哪些灯，state ^ adj[u] 就是按下后的状态。把开关分成两半：前半用 mp[state] 记录最少操作数，后半枚举出 state 后，前半需要补上的正是 ((1LL<<n)-1) ^ state——两半异或，刚好得到全亮的位串。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=45;
int adj[N]; 
map<int,int> mp; // 本模板用有序 map；每次查询 O(log 状态数)
int n,m,ans=1e18;

void dfs1(int step,int max_step,int state,int cnt){
	if(step>max_step){
		if(mp.count(state)) mp[state]=min(mp[state],cnt);
		else mp[state]=cnt;
		return;
	}
	dfs1(step+1,max_step,state,cnt);
	dfs1(step+1,max_step,state^adj[step],cnt+1);
}

void dfs2(int step,int max_step,int state,int cnt){
	if(step>max_step){
		int target=((1ll<<n)-1)^state; 
		if(mp.count(target)){
			ans=min(ans,cnt+mp[target]);
		}
		return;
	}
	dfs2(step+1,max_step,state,cnt);
	dfs2(step+1,max_step,state^adj[step],cnt+1);
}

void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) adj[i]=(1ll<<(i-1));
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		adj[u]|=(1ll<<(v-1));
		adj[v]|=(1ll<<(u-1));
	}
	
	int mid=n/2;
	dfs1(1,mid,0,0);
	dfs2(mid+1,n,0,0);
	cout<<ans<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

八、渐进式实战练习题单

本题单按思维深度与代码实现复杂度分为三个阶梯，覆盖从普及组至省选级别的核心考点。

1. 第一阶梯：网格状压与状态过滤（建立一维到二维的映射）

该阶段侧重训练位运算的熟练度，以及如何在多维 DP 中运用状态掩码进行剪枝。

1. 洛谷 P1879 [USACO06NOV] Corn Fields G
   • 训练指引：基础网格状压。严格应用地形掩码，熟悉同行不相邻的二进制校验。
2. 洛谷 P1896 [SCOI2005] 互不侵犯
   • 训练指引：增加国王总数限制，状态由二维扩展为三维 $dp[i][S][k]$；国王还攻击斜上方，因此跨行除了 s1&s2，还要检查 (s1<<1)&s2 和 (s1>>1)&s2。
3. 洛谷 P2704 [NOI2001] 炮兵阵地
   • 训练指引：攻击范围扩张至距离 2。导致第 $i$ 行的状态不仅受第 $i-1$ 行限制，还受第 $i-2$ 行限制。需要定义 $dp[i][S1][S2]$ 进行滚动数组优化，是网格状压的毕业级题目。

2. 第二阶梯：集合推演与 TSP 模型（突破排列组合的界限）

该阶段侧重将实际的图论或排列问题转化为集合推进，处理复杂的代价累加。

1. 洛谷 P1433 吃奶酪
   • 训练指引：浮点数 TSP 问题。数据量极小（$N \le 15$），适合用于第一次手写 TSP 状态转移方程。
2. 洛谷 P1171 售货员的难题
   • 训练指引：标准 TSP 模板。必须使用位运算完成集合剥离，重点关注初始化逻辑与终局状态的汇总。原题 $2\le n\le20$、$1\le dist<1000$，整条回路小于 20000。第三节的 long long 表约占 168 MiB；内存紧时可只把它改成 int32_t dp[M][N]（约 84 MiB），保留其他变量的 64 位设置。此时沿用 memset(dp,0x3f,sizeof dp)，匹配的无穷大是 0x3f3f3f3f，不是 1e18；把 ans 初值也改成 0x3f3f3f3f，转移改用 if(dp[pre_s][j]+dist[j][i]<dp[s][i]) dp[s][i]=dp[pre_s][j]+dist[j][i];，避免 min 的两参数类型不同而编译失败。不要顺手把其他题的方案计数表也改成 32 位。
3. 洛谷 P3052 [USACO12MAR] Cows in a Skyscraper G
   • 训练指引：状压 DP 与背包问题的结合。求解将集合 $S$ 装入电梯的最少组数与当前电梯剩余空间，状态定义为 pair<int, int> 具有极佳的思维拓展性。

3. 第三阶梯：折半搜索与高阶复合（挑战复杂度极限）

该阶段面向数据范围游走在传统算法盲区的题目，侧重解题视角的切换。

1. 洛谷 P2962 [USACO09NOV] Lights G
   • 训练指引：折半搜索基础。练习使用哈希表（或排序后二分）完成两端状态的拼凑。
2. 洛谷 P4799 [CEOI2015 Day2] 世界冰球锦标赛
   • 训练指引：折半搜索求解超大容量背包（$N \le 40, M \le 10^{18}$）。分别处理出两部分所有可能的子集和，对其一排序后，利用 upper_bound 快速统计合法方案数。
3. 洛谷 P3959 [NOIP2017 提高组] 宝藏
   • 训练指引：历年 NOIP 中难度极高的状压 DP。需要在状态压缩的基础上，引入“树的深度”作为 DP 维度，考察状态展开与生成树性质的深度融合。