状态压缩dp-蒙德里安的梦想

题目链接：

291. 蒙德里安的梦想 - AcWing题库https://www.acwing.com/problem/content/description/293/

f[i][j]表示：前 i - 1 列已经放好，并且从第i - 1 列向第 i 列延申的状态是 j

核心：
摆放的小方格方案数 等价于 横着摆放的小方格方案数

如何判断当前方案是否合法？
遍历每一列，i列的方案数只和i-1列有关系

1.   j&k==0， i-2列伸到i-1的小方格 和i-1列放置的小方格 不重复。
2.   每一列，所有连续着空着的小方格必须是偶数个

#include<bits/stdc++.h>
using namespace std;

const int N = 10, M = 1 << N;
//M 二进制的每一位存储一位状态

int st[M];
//储存每一列上合法的摆放状态

long long f[N][M];
//f[i][j]表示：前 i-1 列已经放好，并且从第i-1 列向第 i列延申的状态是j

// & 只有两位都为 1 才为 1
// | 有一个 1 就是 1
// ^ 两数不同为 1

int main()
{
    int n, m;   cin >> n >> m;
    for(int i = 0; i < 1 << n; i++)//枚举每一列的占位状态中那些是合法的
    {                              //i * 2的 n次方，i的 2进制数左移 n位， 
                                   //一共 n 列，每一个格子有两种情况，为 0（不放），为 1（放）
        int cnt = 0;
        // 记录一列中 0 的个数
        st[i] = true;
        for(int j = 0; j < n; j++)//从低到高枚举每一位
            if(i >> j & 1)//如果该位为 1
            {
                if(cnt & 1)//cnt 为奇数时为真
                //cnt & 1 为真，表示之前连续的 0 为奇数
                st[i] = false;
                cnt = 0;
            }
            else    cnt ++;
            // 该位为 0, 0 的个数++
        if(cnt & 1) st[i] = false;
        //到末尾了 判断一下前面 0 的个数
    }
    
    f[0][0] = 1;
    //不存在 -1列，所以第 0行第 0列 不会有延伸出来的横放小方块
    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]))
            // 两个转移条件： 
            //i 列和 i - 1列同一行不同时捅出来 ； 
            //本列捅出来的状态 j 和上列捅出来的状态 k 求或,
            //得到上列是否为奇数空行状态，奇数空行不转移。
            //st[j | k] == 1 表示 在 i 列状态 j， i - 1 列状态 k 的情况下是合法的.
                f[i][j] += f[i - 1][k];
                //状态转移
        }
    }
    cout<< f[m][0];
    //前 m - 1列已经放置好， 且没有m - 1列向 m 列延伸出
    return 0;
}