模板

状态压缩

状态压缩指的是用较小的数据结构（如整数或位掩码）来表示一个可能的状态或组合，从而减少存储空间和计算复杂性

• 当两个数据分析特别大的时候，我们可以考虑使用二进制来实现$0/1$的分类;
• 下面举例使一个数组的分为 a b两组,找到 max( $\sum a$ , $\sum b$ ) 中的最小值
• a 代表一个分类 b 代表一个分类

cin >> n;
for(int i = 0; i < n; i ++) cin >> k[i];
for(LL state = 0; state < 1LL << n; state ++){           ---> A 
    a = 0, b = 0;										
    for(int i = 0; i < n; i ++){					   	 ---> B
        if(state >> i & 1) a += k[i];
    	else b += k[i];
    }
    ans = min(ans, max(a, b));                           ---> C

• state表示了一个被压缩的状态 $\to$ 用long long 表示一个被分类的状态

Note

A：实际上是表示了$2^n$种状态 1LL << n 等效于 $2^n$

B：二进制位一共有n位，i 从零到 n 解 state二进制位

• 对于每个元素 k[i]，根据 state 的二进制位判断该元素属于组 a 还是组 b

C: 刷新ans,这确保了 ans 始终存储的是所有分组方式中最小的最大和

例子解释，当 n = 3 时

每个 state 的二进制位表示每个元素属于哪一组。例如，对于 n = 3（有 3 个元素的情况）：

• state = 0（000）：所有元素都在组 b
• state = 1（001）：第一个元素在组 a，其余元素在组 b
• state = 2（010）：第二个元素在组 a，其余在组 b
• state = 3（011）：第一个和第二个元素在组 a，第三个在组 b
• …
• state = 7（111）：所有元素都在组 a

Tip

状态压缩的复杂度为 $O(2^n)$ 在 $n>29$ 时大概率TLE