在动态规划的题型中,一般叫什么DP就是怎么DP,状压DP也不例外

所谓状态压缩,一般是通过用01串表示状态,充分利用二进制数的特性,简化计算难度。举个例子,在棋盘上摆放棋子的题目中,我们可以用1表示当前位置摆放棋子,用0表示当前位置不摆放棋子。

这样的话,就能够直接运用许多二进制运算的特性来实现对时间和空间的优化

例如:如果给你一个\(n*m\)的棋盘,让你放棋子,但是棋子两两不能相邻,求方案数

我们仅考虑暴力枚举每一行的情况,如果是普通用数组来存储,判断的时候对于相邻两行需要一个数一个数的看,不论是时间还是空间,都很难让人接受

但是如果用一个二进制数来存储每一行的情况,对于相邻两行,我们只需要进行一下与运算,如果有值,就说明不合法,这样不论是时间还是空间上,都进行了极大的优化

当然,这并不是说状压DP就是暴力枚举,这里只是举个例子来解释一下状压DP中的状态压缩这个过程

看完上面这些,还是不知道这是个什么东西,所以我们结合一道题目来演示一下,什么是状压DP

互不侵犯

这是一道非常经典的状压例题,题意过于简单,我们不再赘述

我们首先考虑一下国王的特性:能够攻击到八个方向的棋子。也就是说,如果某个位置放置了棋子,它的九宫格内就不能再放置了。

我们可以将问题拆解,把九宫格看为三行,就可以分开考虑了

首先我们先考虑在当前行的棋子,只要一个棋子的左右没有相邻的棋子,那么就不冲突

再考虑上面那一行,只要一个棋子正上即左右侧上没有棋子则合法

最后再考虑一下下面那一行是否满足条件

那么我们只要枚举所有情况,再判断就可以了

显然,这样做复杂度实在太高了,9*9的棋盘计算到人类灭亡连枚举都枚举不完

看来我们需要把算法优化一下

我们考虑可不可以逐行枚举,先对每行的状态进行判断,在对上面一行和下面一行进行判断。我们会发现这样的做法是可行的,而且判断下一行是没有意义的,因为我们是逐行枚举,下一行还没枚举到有什么好枚举的。那么我们又会发现,这不是递推嘛。可是这样还是有点慢,怎么优化呢?

下面就是状压时刻了

我们可以在一开始将所有行内可行状态存储下来,由于可行状态远远小于总的状态数,这样可以大大优化我们的复杂度。如何判断这种状态是否没有冲突呢?用与运算就可以轻松判断。我们先预处理好第一行的情况,然后递推即可。

下面来看一下代码吧(内附详解)

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cctype>
#define ll long long
#define gc getchar
#define maxn 10
#define maxm 105     //由于可行状态占比极小,所以行内的可行状态不到100
using namespace std;

inline ll read(){
    ll a=0;int f=0;char p=gc();
    while(!isdigit(p)){f|=p=='-';p=gc();}
    while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=gc();}
    return f?-a:a;
}

int get(int x){     //求当前状态中1的数量
    int sum=0;
    while(x){
        ++sum;
        x&=x-1;    //初赛考了,你做对了吗
    }
    return sum;
}

int n,m,N,tot,s[maxm],w[maxm];    //s[i]表示第i种可行状态的具体摆放,w[i]表示第i种状态棋子的个数
ll ans,f[maxn][maxm][maxm];    //ans最终用来统计答案,f[i][j][l]表示第i行状态为第j种摆放l个棋子的方案数
int main(){
    n=read();m=read();N=1<<n;
    for(int i=0;i<N;++i){
        if(i&i<<1)continue;  //如果非零说明有相邻棋子,则不合法
        s[++tot]=i;
        w[tot]=get(i);
        f[1][tot][w[tot]]=1;    //第一行需要单独初始化
    }
    for(int i=2;i<=n;++i)
        for(int j=1;j<=tot;++j)
            for(int k=1;k<=tot;++k){
                if(s[j]&s[k])continue;    //三种与上一行有冲突的情况
                if(s[j]&s[k]<<1)continue;
                if(s[k]&s[j]<<1)continue;
                for(int l=w[j];l<=m;++l)     //这里非常重要!!l的取值影响到f数组的意义,l如果是从w[j]开始,那么f数组表示的是这一行及以前所有放l个棋子的方案数;如果l从w[j]+1开始,那么f数组表示的是到这一行正好有l个棋子的方案数,以前够了l个棋子的方案则没有被记录在这里面。这会影响到最后统计答案的,并且样例太水并不能看出来。这里一定要注意!!!
                    f[i][j][l]+=f[i-1][k][l-w[j]];
            }
    for(int i=1;i<=tot;++i)    //统计答案就很简单了。不过如果是l是另一种写法还需要枚举1~n
        ans+=f[n][i][m];
    printf("%lld",ans);
    return 0;
}

这就是状压DP,你是否理解了呢?不妨自己打一遍代码,能够加深理解哦。

例题

中国象棋

玉米田

染色(一道我认为可用四进制状压解决的题目,如果有神仙成功了,希望能够告诉我一声,以证明我没口胡错)

山贼集团

茫茫人海相遇也算缘分,点个推荐好不好\(QwQ\)