imicola 状态压缩
状态压缩

状态压缩

391 字 · 约 1 分钟

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

  • 当两个数据分析特别大的时候,我们可以考虑使用二进制来实现0/10/1的分类;
  • 下面举例使一个数组的分为 a b两组,找到 max( ∑a\sum a , ∑b\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
cpp
  • state表示了一个被压缩的状态 →\to 用long long 表示一个被分类的状态