526互联

【状压DP】蒙德里安的梦想

发布时间 2023-03-22 21:13:01作者: 阿新的杂记

image

导读 ^ _ ^

何为状态压缩？

状态压缩的核心是对二进制的理解
我们把一个状态表示成二进制
从而用一个整数表示出各种状态
在dp操作做，我们用位运算的角度去判断并且执行相应的操作

蒙德里安的梦想

Snipaste_2022-12-31_15-16-02.png

思路

如果横着放确定，那么剩下的就是只能竖着放
如何表示每行状态，我们将其用二进制去思考，即每个数都是二进制。
image.png
分类讨论：
image.png
位运算的补充说明：
所以要提取处理一下st布尔数组
image.png
为什么后面还要对cnt进行判断？
因为每次都是从1开始判断，需要处理一下最后的一段
image.png

代码实现

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 12, M = 1 << 12;
long long f[N][M];
bool st[M];
int n,m;

int main( ) {
    while(cin >> n >> m, n || m) {
        memset(f, 0, sizeof(f));
        //预处理st数组，对某种状态不能竖着放的排除
        for (int i = 0; i < 1<<n; i++) {
            int cnt = 0;
            st[i] = true;
            for (int j = 0; j < n; j++) {
                if(i >> j & 1) {
                    if(cnt & 1) st[i] = false;
                    cnt = 0; 
                }
                else cnt++;
            }
            if(cnt & 1) st[i] = false;
        }
       
        f[0][0] = 1;//棋盘是从第0列开始，没有-1列，所以第0列第0行，不会有延伸出来的小方块，即1
        for (int i = 1; i <= m; i++) 
           for (int j = 0; j < 1 <<n; j++)
               for (int k = 0; k < 1<<n; k++) 
                    if((j & k)==0 && st[j | k]) 
                       f[i][j] += f[i-1][k];   
        cout << f[m][0]<< endl;
        //f[m][0]表示 前m-1列的方案数已经确定，从m-1列伸出，并且第m列的状态是0的所有方案数
    }

    return 0;
}

#谢谢你的观看！

^ _ ^