状态压缩学习笔记

a_gold_TomAndJerry · 2025-11-29 21:12:44 · 个人记录

1.关于二进制

二进制只由 0 和 1 组成，所以用二进制可以表示所有整数。

同时，由于二进制的特殊性，我们可以把它看做一个全集的子集，用每一位上的数字来决定在全集中处于同一位的元素是否在这个子集中。

这里有基本的位运算操作：

其中 S 为全集中的某个子集。

不难发现，当一个数转为二进制时，它最低位的 1，也就是 lowbit，决定了它最多能被 2 的多少次方整除。设这个数为 x，lowbit(x)-1 为 n，则一定有 2^n|x 且不存在更大的 n 满足条件。

这个证明其实很简单，只要根据二进制的定义推就可得证。

同时，二进制还有另外一个性质：设一个数 x，则：

由第一个性质可以知道二进制可以用于枚举方案数。所以对于某些存在性问题，可以选用二进制来进行更好看便捷的枚举。

2.状态压缩动态规划

这东西其实和爆搜差不多，只不过更加美观了。

但是我还是不会做

大体思路就是枚举所有的方案数，判断当前枚举的方案数是否符合条件，若符合就对其做 DP。DP 的状态转移方程还是因题而异的。

这种方法只有在 n\le 20 时才适用，看到 10^6 就老老实实想更好的方法吧。

例题 1：[COCI 2015/2016 #2] GEPPETTO

这道题就是典型的状压 DP，N 最大只有 20。

对于每个数的二进制，把 0 看做不放第 i 个原材料，1 看做放。因此对 0 \sim 2^N-1 种状态进行枚举（即从 0 开始枚举到 2^N-1）。对于每种状态，检查是否有冲突的原材料，最后输出总方案数。时间复杂度 \mathcal{O}(2^N\times M)，即使看起来很大，对于这道题也是绰绰有余的。

AC Code：

#include<bits/stdc++.h>
using namespace std;
int n,m,ans=0;
pair<int,int> a[41]; 
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i) scanf("%d%d",&a[i].first,&a[i].second);
    for(int i=0;i<(1<<n);++i){
        bool flag=0;
        for(int j=1;j<=m;++j){
            if(i&(1<<(a[j].first-1))&&i&(1<<(a[j].second-1))){
                flag=1;
                break;
            }
        }
        if(!flag) ans++;
    }
    cout<<ans;
    return 0;
}

例题 2：[蓝桥杯 2019 省 A] 糖果

对于每个数的二进制，把 0 看成第 i 种口味无糖，1 看成有糖。所以设 f[i] 表示所有的糖状态为 i 时最少需要购买的包数。在每种状态下，对于每包糖，选择拿或不拿。因此可以列出状态转移方程 f[i|c[j]]=\min(f[i|c[j]],f[i]+1)，其中 c[i] 为第 i 包糖的二进制，表示哪些口味是有的。时间复杂度 \mathcal{O}(2^M\times N)。

AC Code：

#include<bits/stdc++.h>
using namespace std;
int n,m,k,f[1<<20],c[1<<20];
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=k;++j){
            int x;
            scanf("%d",&x);
            if(c[i]&(1<<(x-1))) continue;
            else c[i]+=(1<<(x-1));
        }
    }
    memset(f,0x3f3f3f3f,sizeof(f));
    f[0]=0;
    for(int i=0;i<(1<<m);++i){
        for(int j=1;j<=n;++j) f[i|c[j]]=min(f[i|c[j]],f[i]+1);
    }
    if(f[(1<<m)-1]==0x3f3f3f3f) cout<<-1;
    else cout<<f[(1<<m)-1];
    return 0;
}

例题 3：[USACO06NOV] Corn Fields G

这道题要考虑的因素很多。可以先预处理出田状态的二进制，0 表示不能种，1 表示能种。然后对于所有状态，0 表示没有草，1 表示有草，进行枚举。去掉非法的情况（即 1 的左右两边存在 1 或者有 1 的地方不能种草），从第二行开始，对第 i 行进行枚举。同时，对于第 i 行，对第 i-1 行也进行枚举。如果有上下相同或非法就去除，剩下就是对方案数求和。设 f[i][j] 为在第 i 行的状态为 j 时的最大方案数，状态转移方程为 f[i][j]=f[i][j]+f[i-1][k] 。时间复杂度为 \mathcal{O}(2^{2M}\times N)。

AC Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e8;
ll m,n,a[13][13],c[13],h[1<<12],f[13][1<<12];
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j){
            scanf("%lld",&a[i][j]);
            c[i]=(c[i]<<1)+a[i][j];  //预处理 c[i]
        }
    for(int i=0;i<(1<<m);++i){
        if(!(i&(i>>1))&&!(i&(i<<1))){  //原理：左右移如果有都是 1 的情况就是非法的
            h[i]=1;  //方案合法
            if((i&c[1])==i) f[1][i]=1;  //初始化
        }
    }
    for(int i=2;i<=n;++i){
        for(int j=0;j<(1<<m);++j){
            if((j&c[i-1])==j&&h[j]){
                for(int k=0;k<(1<<m);++k){
                    if((k&c[i])==k&&!(j&k)&&h[k]){  //如果 j 和 k 有相同的数 !(j&k) 就为假
                        f[i][k]=(f[i][k]+f[i-1][j])%mod;
                    }
                }
            }
        }
    }
    ll ans=0;
    for(int i=0;i<(1<<m);++i) ans=(ans+f[n][i])%mod;  //对 f[n][i] 进行求和
    cout<<ans;
    return 0;
}

额外习题（？）：
[USACO12MAR] Cows in a Skyscraper G
[USACO13NOV] No Change G
[USACO14FEB] Cow Decathlon G

对于额外习题的第一题，我的方法高达 \mathcal{O}(3^n)，但是锣鼓的数据太水还是能 A（要吸氧）。大体思路就是先预处理出每个排列的体积总和，然后对于每一个状态进行拆分，拆成 2 个子集，取原来的方案数与拆开后的方案数加一的最小值。对于某个 i 的子集有以下公式可以枚举：for(int j=i;j;j=(j-1)&i)。这道题有正解，不要根据超时的思路走 qwq。