状压 dp

lalaji2010 · 2024-08-16 09:54:48 · 算法·理论

状态压缩

状态压缩实际上就是将很多个元素的状态表示成一个集合，根据每个元素状态的种数，我们通常在算法竞赛中将其表示成一个 x 进制数。其中，二进制表示的状态压缩后的集合最为常用。

那么我们为什么要这样做呢，请看引例。

引例①

假设我们有 n 个数 a_1,a_2,\dots,a_n ，如果我们要枚举它们的选择情况的集合。

暴搜当然可以啦，不断枚举当前位的选择，时间复杂度 O(n!)。

不妨令二进制下从右往左第 i 个位置为 1 表示 a_i 被选择，为 0 表示 a_i 未被选择，这样只需要枚举 0 到 2^n-1 就可以表示所有的选择情况，时间复杂度 O(2^n)。

我们发现：暴力搜索枚举集合效率低下，而状态压缩枚举集合省掉了许多无用情况，时间复杂度更加优秀。

引例②

在引例①的基础上，假设我们已经枚举出一个集合，想要判断我是否选择了两个相邻的元素。

如果我们枚举状态压缩的集合，我们就会得到几个二进制数，我们可以通过位运算很容易地判断，时间复杂度 O(1)。

而传统的枚举选择情况则需要顺序遍历一遍，时间复杂度 O(n)。

引例③

暴力搜索枚举选择情况是无序的，假设要求状态是可以进行动态规划的，也就是状态可构成一个 DAG 图，暴力搜索往往会打乱 DAG 图的拓扑序。

状态压缩假设从小到大枚举，假设枚举出集合 S，那么比该集合少选择元素的情况一定早就处理过了，便于进行状态转移。并且状态压缩是易于预处理出对答案有价值的集合的，比 dfs 方便很多。

引例就先到这里，下面来看几道状态压缩的简单应用题目。

Ⅰ. HDU1429 胜利大逃亡（续）

分析

显然，这是一道分层图 bfs。我们发现，假设我们携带不同的钥匙到同一个位置（当然不一定非得是门），其产生的结果是截然不同的，所以我们每一次 bfs 进队列的元素不仅要记录到了哪里，还要记录携带着什么钥匙，即只有同样的钥匙集合才不能走到同样的位置。

钥匙很少（\texttt{only 10}），所以记录携带的钥匙集合可以使用数组，也可以使用二进制表示的状态压缩集合。两者本质上是一致的，并且由于该题目无须很多位运算技巧，所以时间复杂度也是难分优劣的。由于二进制数表示集合更节省空间，所以我们使用二进制数表示集合来实现。

case 1

假设我们 bfs 过程中取出一个元素 u，通过四方向扩展 u 又走到了一个合法的钥匙 key（key 是表示该钥匙的字母）的位置，此时代表这个新位置的元素 v 应当重新入队，v 相对 u 而言位置应当发生变化并且其钥匙集合 S 应当执行 S = S | (1 << (key - 'a'));。

case 2

假设我们 bfs 过程中走到了一扇门 door（door 是表示该钥匙的字母），那么能通过的条件应当是 S&(1<<(door-'A')) 为真。

除此之外，记录一下时间，跟一般的广搜思路完全一致，时间复杂度 O(\sum 2^{letter} \cdot nm)，其中 letter=10，表示 10 个字母（A 到 J），因为一个位置至多会被走 2^{letter} 次（钥匙的所有组合），下面上代码。

AC CODE

#include<bits/stdc++.h>
using namespace std;
struct sta{
    int x,y;
    int time;
    int key;
}st;
int n,m,t;
int vis[25][25][(1<<10)+5]; 
char mp[25][25];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
void bfs(sta x){
    queue<sta> q;
    x.key=x.time=0;
    vis[x.x][x.y][x.key]=1;
    q.push(x);
    while(!q.empty()){
        sta tx=q.front();
        q.pop();
        if(mp[tx.x][tx.y]=='^'){
            cout<<tx.time<<"\n";
            return;
        }
        for(int i=0;i<4;i++){
            if(tx.x+dx[i]>n||tx.x+dx[i]<1||tx.y+dy[i]>m||tx.y+dy[i]<1||mp[tx.x+dx[i]][tx.y+dy[i]]=='*'||tx.time+1>=t||vis[tx.x+dx[i]][tx.y+dy[i]][tx.key]) continue;
            sta xx=tx;
            xx.x+=dx[i];
            xx.y+=dy[i];
            xx.time++;
            if(mp[xx.x][xx.y]>='a'&&mp[xx.x][xx.y]<='z') xx.key|=(1<<(mp[xx.x][xx.y]-'a'));
            else if(mp[xx.x][xx.y]>='A'&&mp[xx.x][xx.y]<='Z'&&!(xx.key&(1<<(mp[xx.x][xx.y]-'A')))) continue;
            vis[xx.x][xx.y][xx.key]=1;
            q.push(xx);
        }
    }
    cout<<-1<<"\n";
}
int main(){
    while(cin>>n>>m>>t){
        memset(vis,0,sizeof vis);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>mp[i][j];
                if(mp[i][j]=='@'){
                    st.x=i,st.y=j;
                }
            }
        }
        bfs(st);
    }
    return 0;
}

Ⅱ.洛谷 P2622 关灯问题Ⅱ

分析

数据很小，考虑状态压缩，1 表示开，0 表示关。

最初状态是全开即 2^n-1。

目标状态是全关即 0。

两者之间的最短路径，考虑广搜。一开始的全开是按了 0 次按钮，对于每次从队列取出的元素尝试再按 1 次按钮，枚举按的是哪个按钮，将按下去后的状态再次入队列，同时记录操作次数即可，时间复杂度 O(2^nmn)。

位运算技巧很简单，这里不展开说了，详见代码。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[105][15];
int dp[(1<<10)+5];
int vis[(1<<10)+5];
void bfs(int x){
    queue<int> q;
    dp[x]=0;
    vis[x]=1;
    q.push(x);
    while(!q.empty()){
        int tx=q.front();
        q.pop();
        if(tx==0){
            cout<<dp[tx]<<"\n";
            return ;
        }
        for(int i=1;i<=m;i++){
            int xx=tx;
            for(int j=1;j<=n;j++){
                if(a[i][j]==1) xx&=((1<<n)-1)-(1<<(j-1));//关掉这盏灯
                else if(a[i][j]==-1) xx|=(1<<(j-1));//打开这盏灯
            }
            if(!vis[xx]){
                vis[xx]=1;
                q.push(xx);
            }
            dp[xx]=min(dp[xx],dp[tx]+1);
        }
    }
    cout<<-1<<"\n";
} 
int main(){
    memset(dp,0x3f,sizeof dp);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    bfs((1<<n)-1);
    return 0;
}

总结

最后附上转载于 MinimumSpanningTree 的文章里的位运算技巧。

到这里，我们已经初步理解了状态压缩的基本应用和优势，接下来进入正文部分。

状态压缩动态规划

其实就是用状态压缩的性质优化动态规划的状态转移，减少转移代价。下面直接看例题。

HDU-1565 方格取数(1)

这是一道经典的状态压缩 dp 题。

分析

数据很小，显然的状压 dp。

这种题很套路，取的两个数不能挨着，那么定义 f_{i,j} 表示取完第 i 行，第 i 行取法为 j 的答案（j 表示选取集合）。

这样定义状态的原因是，第 i 行的取法与第 i-1 行有关；在每一行选取的是一个集合，所以第二维表示选择的集合。

暴力做法就是每一行都暴搜选择情况，然后暴搜上一行选择情况，判断合法状态的进行转移，时间复杂度爆炸。

上文提到，状态压缩可以优化 dfs，所以对于每一行，可以使用状态压缩枚举集合来优化暴搜。

具体来说：对于每一个集合 j 再枚举 i-1 时的所有选择集合 k，将合法的集合尝试状态转移即 dp_{i,j}=\max(dp_{i,j},dp_{i-1,k}+w)，w 为集合 j 选择的元素之和，最后答案就是最后一行所有合法集合的答案的最大值。

使用状态压缩判断是否合法也很简单，集合 j 没有左右相邻的 1 时，s&(s>>1) 值为 0。集合 j,k 上下同一个位置上不全是 1 时，j&k 的值为 0。

这样我们就有了 O(2^{n} \cdot 2^{n} \cdot n)=O(2^{2n}n) 的做法，但是显然还是过不了。

这样做很慢的原因就是有很多无效的状态枚举，比如在枚举 j 时，在集合大小 n 确定的情况下，有非常多的状态本身就有相邻的 1，上文提到，这里其实完全可以预处理出来合法集合，然后只枚举合法的集合即可，而不用每次都去枚举一遍全集，当然枚举 k 时同理。

AC CODE

#include<bits/stdc++.h>
using namespace std;
long long n,a[25][25],dp[21][18005],s[18005],tot=0;
long long res=0;
long long calc(int i,int s){
    long long ans=0;
    int j=n;
    while(s){
        if(s&1) ans+=a[i][j];
        s>>=1;
        j--;
    }
    return ans;
}
int main(){
    while(cin>>n){
        res=0;
        tot=0;
        memset(s,0,sizeof s);
        memset(dp,0,sizeof dp);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                cin>>a[i][j];
            }
        }
        for(int i=0;i<(1<<n);i++){
            if((i&(i>>1))==0) s[++tot]=i;
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=tot;j++){
                long long w=calc(i,s[j]);
                for(int k=1;k<=tot;k++){
                    if((s[j]&s[k])==0){
                        dp[i][j]=max(dp[i][j],dp[i-1][k]+w);
                    }
                }
            }
        }
        for(int i=1;i<=tot;i++){
            res=max(res,dp[n][i]);
        }
        cout<<res<<"\n";
    }
    return 0;
}

P1879 [USACO06NOV] Corn Fields G

分析

这道题比上道题又多了一个有些地方不能选择的限制。

其实只需要枚举完每个集合以后判断该集合选的位置是否都能选就好了，集合不合法直接跳过这个集合的寻求转移过程。

一点小区别是这道题最后求的是方案数，那么状态转移时只需要做累加即可。其他的和上一道题一模一样。

AC CODE

#include<bits/stdc++.h>
using namespace std;
const int mod=1e8;
long long n,m,a[25][25],dp[21][18005],s[18005],tot,vis[15][(1<<12)+7],book[15][(1<<12)+7];
long long res;
bool check(int i,int s){
    int j=m;
    while(s){
        if((s&1)&&a[i][j]==0){
            return 0;
        }
        j--;
        s>>=1;
    }
    return 1;
}
int main(){
    cin>>n>>m;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>a[i][j];
            }
        }
        for(int i=0;i<(1<<m);i++){
            if((i&(i>>1))==0){
                s[++tot]=i;
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=tot;j++){
                if(!check(i,s[j])) continue;
                if(i==1) dp[i][j]=1;// 预处理后第一行的每种选择一定合法，初始化为 1
                else{
                    for(int k=1;k<=tot;k++){
                        if(!check(i-1,s[k])) continue;
                        if((s[j]&s[k])==0){
                            dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;
                        }
                    }
                }
            }
        }
        for(int i=1;i<=tot;i++){
            if(!check(n,s[i])) continue;//集合不合法对答案无贡献
            res=(res+dp[n][i])%mod;
        }
        cout<<res<<"\n";

    return 0;
}

P1896 [SCOI2005] 互不侵犯

还是按行来，并且转移只与上一行有关。

这题的答案与状态转移不得不必须需要体现放置个数，我们不妨设 dp[i][j][k] 表示放完第 i 行，总共放置了 j 个，第 i 行放置方案为 k 的方案数。

那么我们在照例枚举完第 i 和第 i-1 行的集合后进行状态转移的时候，应该对于不同的总放置个数进行转移，状态转移方程为 dp[i][j][k]=dp[i][j][k]+dp[i-1][j-cnt[k]][s]。cnt[j] 是 k 里面的放置个数，这个可以在最开始将所有没有相邻 1 的集合选取出来的过程中进行预处理，预处理可以使用内置的__butin_popcount(j)，s 是枚举的第 i-1 行的合法集合。

最终的答案是 \sum_{s=0}^{2^{n}-1} dp[n][k][s]，因为不合法的集合里面本身也是 0 嘛。

AC CODE

#include<bits/stdc++.h>
using namespace std;
const int N=9;
int n,k;
int s[(1<<N)+5],tot=0;
int cnt[(1<<N)+5];
long long dp[15][105][(1<<N)+5];
long long res=0;
int main(){
    cin>>n>>k;
    for(int bit=0;bit<(1<<n);bit++){
        if(!(bit&(bit>>1))){
            s[++tot]=bit;
            cnt[tot]=__builtin_popcount(bit);
            dp[1][cnt[tot]][tot]=1;
        }
    }
    for(int i=2;i<=n;i++){
        for(int j=1;j<=tot;j++){
            for(int bit=1;bit<=tot;bit++){
                if(!(s[j]&s[bit])&&!(s[j]&(s[bit]<<1))&&!(s[j]&(s[bit]>>1))){
                    for(int num=cnt[j];num<=k;num++){
                        dp[i][num][j]=dp[i][num][j]+dp[i-1][num-cnt[j]][bit];
                    }
                }
            }   
        }
    }
    for(int i=1;i<=tot;i++){
        res+=dp[n][k][i];
    }
    cout<<res<<"\n";
    return 0;
} 

P1171 售货员的难题

分析

显然是一道 dp 题目，如果我们暴力尝试每一步走的位置，那么时间复杂度是 O(n!) 的。

前面提到，恰当的枚举状态是可以将暴力搜索的时间复杂度降到 O(2^n) 的，放在本题可以接受。

如果我们先枚举状态，表示哪些村庄去过，那些村庄没去过，那么容易设出状态：f[i][j] 表示访问状态为 i 时，最后到达 j 的最短路。

为什么要有一个 j 呢？因为最后走完所有村庄还要再走回 1 号村庄，而不同村庄走回去的费用不同，最后统计答案时需要明确从不同村庄回去的费用。

考虑状态转移。

先从小到大枚举访问状态 i，再枚举该状态最后到达 j（先表示出待转移的状态）。

当前状态一定是由比当前状态少访问一个 j 而其他村庄访问情况相同的状态转移而来的。

同时我们能保证比当前状态少访问一个 j 的状态比当前状态小，故必定在当前状态之前被枚举到并转移好状态，保证了dp 的无后效性。

所以考虑从非 j 而当前状态访问过的村庄的最小转移代价即可。

此番状态转移思想与 Floyd 有异曲同工之妙。

注意几个小细节：

1. 第一个村庄是必定访问过的，所以状态从 1 开始枚举，每次加 2。

2. 所有村庄都访问过以后还要走回起点，统计答案时考虑走完所有村庄时最后一个走到的村庄，因为还要加上从该村庄走回起点的费用。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int n,a[25][25],dp[(1<<20)+5][25];
int main(){
    memset(dp,0x3f,sizeof dp);
    dp[1][1]=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    for(int i=3;i<(1<<n);i+=2){
        for(int j=2;j<=n;j++){
            if(!((i>>(j-1))&1)) continue;//j 是 i 状态最后访问的点，所以必须在 i 状态中访问过
            for(int k=1;k<=n;k++){
                if(j==k||!((i>>(k-1))&1)) continue;//从非 j 而当前状态访问过的点转移而来
                dp[i][j]=min(dp[i][j],dp[i^(1<<(j-1))][k]+a[k][j]);
            }
        }
    } 
    int mn=0x3f3f3f3f;
    for(int i=1;i<=n;i++){
        mn=min(mn,dp[(1<<n)-1][i]+a[i][1]);//考虑从不同位置走回起点
    }
    cout<<mn<<"\n";
    return 0;
}

AT_dp_o Matching

分析

我们设 f[i][j] 表示匹配完了男生的前 i 个，女生的选择匹配情况为 j 的方案数。这和前面的棋盘放置问题的做法有异曲同工之妙。

考虑状态转移。

首先要表示待转移状态，枚举男生匹配完了第 i 个时，女生的选择集合 j。

易知女生的选择数量 num 必须等于 i（要不然就不是完全匹配了），然后该状态可以由前 i-1 个男生匹配了 num-1 个女生（当然，这些女生必须在当前状态 j 中都被选了）的状态并让 1 个女生（必须在当前状态 j 中被选了）和第 i 个男生配对转移而来，当然还有一个条件是该女生和第 i 个男生 互相爱慕 兼容。

这样做的时间复杂度是 O(2^{n}n^{2}) 的，卡卡常可能能过？ 考虑优化。

我们发现，上文的 num 恒等于 i，所以我们干脆不用枚举 i。同时，状态中 f[i][j] 的 i 取决于 j，f[i-1][j_1] 的状态必定不会被存到 f[i][j_1] 中，故可以压掉 i 这一维。

依照分析求解即可。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int n;
int a[25][25];
int dp[(1<<21)+5];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    dp[0]=1;
    for(int i=0;i<(1<<n);i++){
        int num=__builtin_popcount(i);
        for(int j=1;j<=n;j++){
            if(!(i&(1<<(j-1)))) continue;
            if(a[num][j]){
                dp[i]=(dp[i^(1<<(j-1))]+dp[i])%1000000007;
            }
        }
    }
    cout<<dp[(1<<n)-1]<<"\n";
    return 0;
}