题目

n×m的棋盘可以摆放不同的1×2小方格的种类数。

题目选自《算法竞赛进阶指南》，用于状态压缩的理解，较难。

考点

状态压缩dp ，二进制数据预处理 ，二进制运算

分析

摆放方块的时候，先放横着的，再放竖着的。
总方案数等于只放横着的小方块的合法方案数。
状态压缩的dp：用一个N位的二进制数，每一位表示一个物品，0/1表示不同的状态。‘

dp状态表示

  1. 状态数组f[i][j]:表示已经将前 i -1 列摆好，且从第i−1列，伸出到第 i列的状态是 j的所有方案。其中j是一个二进制数，用来表示哪一行的小方块是横着放的，其位数和棋盘的行数一致。
  2. 状态是如何转移
    需要看 第i-2 列是怎么转移到到第 i-1列的。假设此时对应的状态是k（第i-2列到第i-1列伸出来的二进制数，比如00100），k也是一个二进制数，1表示哪几行小方块是横着伸出来的，0表示哪几行不是横着伸出来的。对应的方案数是 f[i−1,k]。
    3.k需要满足说明条件 （(j & k) == 0 && st[j | k]） 关于这个条件的意义在代码注解里有解释

代码

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int N = 12,M = 1 << N;
long long f[N][M];
bool st[M];
//记录合法状态的数组
vector<vector<int>> state(M);
int n,m;

int main()
{
    //n为宽 m为长 
    while(cin >> n >> m,n || m)
    {
        //预处理1 ——排除每列出现奇数个连续0的情况
        //因为列状态如果含有奇数个连续的0 说明竖着放长方形时无法填满 不合法
        for(int i = 0;i < 1 << n;i++)
        {
            int cnt = 0;//记录连续0的个数
            bool isValid = true;//某种状态没有奇数个连续的0则标记为true
            for(int j = 0;j < n;j++)//从上到小遍历当前列
            {
                //i是一个十进制的数字
                //i>>j 是循环从i中提取二进制的j位
                //&1为判断该位是否为1，如果为1进入if
                if((i >> j) & 1) 
                {
                    //cnt & 1为真则该状态包含奇数个0
                    //因为cnt如果是个奇数那么cnt二进制最后一位一定是1 
                    //1 & 1 则为真 满足if条件
                    if(cnt & 1)
                    {
                        isValid = false;
                        break;
                    }
                }
                else cnt ++; //j位为0 cnt++
            }
            //处理可能残留的cnt
            if(cnt & 1) isValid = false;
            //状态i是否有奇数个连续的0的情况存入st数组
            st[i] = isValid;
        }
        
        //预处理2
        //判断第i-2列伸出来的和第i-1列伸出去的是否冲突
        for(int j = 0;j < 1 << n;j++) //j代表第i列所有状态
        {
            state[j].clear();//清理数组,因为这些逻辑是在while循环内不是处理一组数据
            for(int k = 0;k < 1 << n;k++)//k代表第i-1列所有状态
            {
                //两列的状态 存在 不能重叠  (j & k) == 0
                //j | k用于合并在i-1列有多少个1
                //st[j | k]用于排除不合法的状态
                if((j & k) == 0 && st[j | k]) state[j].push_back(k);
                //二维数组state[j]表示在数组的第j行 相当于j作为key
                //j表示第i列“真正”可行的状态，
                //如果第i-1列的状态k和j不冲突则压入state数组中的第j行。 k相当于value
                //“真正”可行是指：既没有前后两列伸进伸出的冲突；又没有连续奇数个0。
            }
        }
        
        //dp部分
        memset(f,0,sizeof f);//全部初始化为0，因为是连续读入，这里是一个清空操作。类似上面的state[j].clear()
        f[0][0] = 1;
        //虚构的状态数组初始化
        //f[0][0]第一个0表示第0列，
        //第二个0表示第0列伸出去的状态为0，
        //那么第0列的方案只能是竖摆这一种，至于不需要考虑竖摆的奇偶数合法性
        //因为第0列本身就是为了推导第1列而虚构的。
        //如果假设f[0][0]=0，那么后面所有的递推就无从谈起。
        
        //dp
        for(int i = 1;i <= m;i++)//遍历每一列
        {
            for(int j = 0;j < 1 << n;j++)//遍历每列的状态
            {
                for(auto k : state[j]) //遍历第i-1列的合法的状态k，并进行转移
                {
                    f[i][j] += f[i-1][k];//当前列的方案数就等于之前的第i-1列所有状态k的累加。
                }
            }
        }
        
        //f[m][0]表示 前m-1列都处理完，并且第m-1列没有伸出来的所有方案数。
        cout << f[m][0] << endl;
    }
    return 0;
}