6.状态压缩DP

将一个十进制的整数转化为二进制数，每一位表示一种状态

AcWing 291. 蒙德里安的梦想

实现思路：先放横着的，再放竖着的。

总方案数，等于只放横着的小方块的合法方案数。（放完横着的方块之后，竖着的只能被动填充进去，不需要额外进行竖着的情况）

方案合法的条件是：当横着的方块放完后，竖着的小方块恰好能把剩余的地方全部填满。

那如何判断方案是否合法呢？即怎么看竖着的小方块是否能把剩余部分填满呢？因为是竖着放的，所以可以按列来看，每一列的内部，只要所有连续的空余小方块的个数为偶数，即可。

  • 状态表示：f[i][j]表示前i-1列已经摆好，且从第i-1列是否有伸出一格到第i列的情况（这个情况用j表示）的所有方案数。

    • 对于j：j是一个二进制数，位数与棋盘的行数相等，比如N=5，M=5的棋盘，j为5位的二进制数(XXXXX)_2，但在程序中还是用十进制数表示。（所以要用位运算来判断某一位是1或0）

    • 什么叫j表示从第i-1列伸出一格到第i列的情况？如下图，第i列的第1，2，5个格子，是从i-1列伸过来的。此时的状态j为 (11001)_2，即对于第i列的所有格子，第1，2，5个格子被伸出来占据了（j是个二进制数，若该列的某一行，有被前面的列伸出来一格，则用1表示，否则用0表示），那么这些个位置被侵占了，就不能再横放了。

    • 这样对f[i][j]更通俗的理解就是第i列的横放情况，由j的二进制表示出第i列哪些行可以横放

  • 状态转移：既然第i列固定了，我们需要看 第i-2 列是怎么转移到到第 i-1列的（看最后转移过来的状态）。假设此时对应的状态是k（第i-2列到第i-1列伸出来的二进制数，比如00100），k也是一个二进制数，1表示哪几行小方块是横着伸出来的，0表示哪几行不是横着伸出来的。

    它对应的方案数是 f[i−1,k]，即前i-2列都已摆完，且从第i-2列伸到第i-1列的状态为 k 的所有方案数。

  • 那k需要满足什么条件，才能够从f[i - 1][k]转移到f[i][j]呢？

    • ①k和j不能冲突，也就是第i-1列和第i列的不能有重叠的1，即两列的相同行不能同时为1（不能同时有前一列伸过来的）。如下图，在第一行k的二进制位为1，j的二进制位也为1，那么第i列就不能再横放东西了。转化为代码判断就是** (k & j ) ==0** ，表示两个数相与，如果两有对应位同时为1，则相与结果为1，否则为0即没有冲突。

    • ②既然从第i-1列到第i列横着摆的，和第i-2列到第i-1列横着摆的都确定了，那么第i-1列 空着的格子就确定了，这些空着的格子将来用作竖着放。如果 某一列有这些空着的位置，那么该列所有连续的空着的位置长度必须是偶数（即不能有奇数个0）。设置一个st[]数组表示的是这一列连续0的个数的情况，若为true表示连续偶数个0（合法状态），否则为false。体现到代码判断第i-1列满足竖放的合法状态：**st[k|j]=true**，

      • 解释：第i-1列中1的总个数，就是当前 第i-1列的到底有几个1，即哪几行是横着放格子的

        st[k]表明第i-2列插入到i-1列的1的个数，i-1列被动生成的1

        st[j]表明第i-1列插入到i列的1的个数，也就是i-1列自己生成的1

  • 最后结果输出f[m][0]

注：对于f[0][0]=1和最后输出f[m][0]理解：数组下标从0开始表示实际棋盘的第一列，放f[][]表示当前列的横放情况,f[0][0]表示当前一列没有伸过来的（因为前面根本没有列），所以也就没有横放的情况，只有竖放的情况，即f[0][0]=1。所以输出f[m][0]表示第m列不横放，这也是合理的，如果第m列横放了，那就超出m列的范围了。

其他理解：AcWing 291. 蒙德里安的梦想 - AcWing

AcWing 291. 蒙德里安的梦想 - AcWing

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=12,M=1<<N;
long long f[N][M];
bool st[M];//记录当前连续0的个数是否为偶数，即合法状态true
int n,m;
int main(){
    
    while(cin>>n>>m,n||m){
        memset(f,0,sizeof f);//初始化为0
        //先预处理得到每一列连续0的个数 是偶数还是奇数
        for(int i=0;i<1<<n;i++){
            st[i]=true;
            int cnt=0;//记录0的个数
            
            for(int j=0;j<n;j++){//遍历当前列的每一行
                
                if(i>>j & 1){//取得当前行的一位 若为1
                    //判断之前记录的0的个数 是否为奇数
                    if(cnt & 1) st[i]=false;//若为奇数 标记为false 不合法
                }
                //取得当前行的一位 为0
                else cnt++;
            }
            //得到该列0个数的最终结果 判断是否是否合法
            if(cnt & 1) st[i]=false;//若个数为奇数 不合法
        }
        
        f[0][0]=1;
        
        //开始DP
        for(int i=1;i<=m;i++)//从列开始
            for(int j=0;j<1<<n;j++)//第i列情况
                for(int k=0;k<1<<n;k++)//第i-1列情况
                    if((j&k)==0 && st[j|k])//若没有冲突 且连续0的个数是偶数 
                        f[i][j]+=f[i-1][k];//合法
        
        cout<<f[m][0]<<endl;
    }
    return 0;
}

AcWing 91. 最短Hamilton路径

  • f(i,j)表示从0号点到j号点，且中间经过点的状态是i（和上题类似，用二进制表示，位为1就表示某点经过，同样要进行位运算来获得每一位。如 1 1 1 0 1 表示第0，1，2，4被走过）的最短路径长度。
  • 集合划分：最后一个点是j，按倒数第二个点划分，若倒数第二个点是k，即从0号点经过一系列不重复的点到达点k，再经过点k到达终点j。同时在这个状态i中就不能再包括点j了（因为路径要不重不漏），要再状态i中除去j。
  • 最终状态转移方程为：**f[i][j]=min(f[i][j],f[i-1<<j][k]+a[k][j])；**因为i是二进制数，除去j点就表示使j位置上的二进制位由0后改为1，即相减。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=21,M=1<<21;
int n;
int f[M][M],a[N][N];
int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>a[i][j];
    
    memset(f,0x3f,sizeof f);//初始化图上各点距离为无穷大
    f[1][0]=0;//从0开始到0本身的距离为0
    
    for(int i=1;i<1<<n;i++)
        for(int j=0;j<n;j++)//枚举0到n号点
            if(i>>j & 1)//为1 要到达点j
                for(int k=0;k<n;k++)//枚举倒数第二个点k
                    if((i-(1<<j)) >> k)//如果k点在路径中
                        f[i][j]=min(f[i][j],f[i-(1<<j)][k]+a[k][j]);
    //从0 经过所有点 到达 n-1号点
    cout<<f[(1<<n)-1][n-1];
    
    return 0;
}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。