JZTXT

状压dp学习笔记

发布时间 2023-10-08 22:18:46作者: Miya555

"此刻发生的所有事，都是你过去选择的结果。"

最近打模拟赛在状压dp上总是没有一点思路。来重学一遍。

 

状态压缩：通过一串 0 1 码来清晰地表示一个集合的状态。同时，在确定了最低位的前提下，一串 0 1 码与一个二进制数一一对应。

 

其本质上是进行了两次操作：

  1. 给这个集合的每个状态一个编号。
  2. 通过这个编号，轻易地访问该状态。

 

状压dp常见题型：

  1. 棋盘式，求方案数。
  2.  集合，求最短路径。

 

首先，我们需要掌握一些位运算的小技巧：

1.判断一个数字x二进制下第i位是不是等于1。（最低第 1 位）

方法：if(((1<<(i−1))&x)>0)

将1左移 i -1 位，相当于制造了一个只有第 i 位上是 1，其他位上都是 0 的二进制数。然后与 x 做与运算，如果结果 > 0， 说明 x 第 i 位上是 1，反之则是 0。

2.将一个数字x二进制下第 i 位更改成 1。

方法：x=x|(1<<(i−1))

证明方法与 1 类似。

3.将一个数字x二进制下第 i 位更改成 0。

方法：x=x&~(1<<(i−1))

4.把一个数字二进制下最靠右的第一个1去掉。

方法：x=x&(x−1)

 

下面是例子。

1.P2622 关灯问题

题意略。

可以发现n的范围<=10。此时想到状压dp的时间复杂度为指数级别，刚好符合本题要求。

考虑从0开始不断向上枚举，遍历 m 个控制效果。通过某个控制效果可以达到状态 t ，那么设 fs 表示到达状态 s 时所需要的最小步数。

得到：

              ft=minzj(i)=t { fi }+1

 

 

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=12,maxm=1025;
int n,m,t,f[1<<maxn],a[maxm][maxn];
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            cin>>a[i][j];
    fill(f+1,f+maxm+1,inf);
    for(int i=0;i<(1<<n);i++)
        for(int k=1;k<=m;k++){
            t=i;
            for(int j=0;j<n;j++)
                if((a[k][j+1]==1&&!(i&1<<j))||(a[k][j+1]==-1&&(i&1<<j)))
                    t^=(1<<j);
            f[t]=min(f[t],f[i]+1);
        }
    if(f[(1<<n)-1]==inf) cout<<"-1"<<endl;
    else cout<<f[(1<<n)-1]<<endl;
    return 0;
}

 

#注意，其实本题的正解应当为记忆化搜索或者状压最短路。状态是有后效性的。状压dp的做法在洛谷上已经被hack。但这种做法不乏为一种很好的思路。所以还是放这了。