291 蒙德里安的梦想（状态压缩dp）

以你之姓@ 2022-09-12 04:57 6阅读 0赞

**1. 问题描述：**

求把 N×M 的棋盘分割成若干个 1×2 的的长方形，有多少种方案。例如当 N=2，M=4 时，共有 5 种方案。当 N=2，M=3 时，共有 3 种方案。如下图所示：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_20_color_FFFFFF_t_70_g_se_x_16][]

**输入格式**

输入包含多组测试用例。每组测试用例占一行，包含两个整数 N 和 M。当输入用例 N=0，M=0 时，表示输入终止，且该用例无需处理。

**输出格式**

每个测试用例输出一个结果，每个结果占一行。

**数据范围**

1 ≤ N，M ≤ 11

**输入样例：**

1 2  
1 3  
1 4  
2 2  
2 3  
2 4  
2 11  
4 11  
0 0

**输出样例：**

1  
0  
1  
2  
3  
5  
144  
51205  
来源：[https://www.acwing.com/problem/content/description/293/][https_www.acwing.com_problem_content_description_293]

**2. 思路分析：**

这道题目属于**状态压缩dp**的入门题目（状态压缩的题目一般数据范围在50以内），思路上还是有一定难度的，比较难想出来状态表示是什么。题目的核心是先放横着的，再放竖着的小方块，总方案数目等于只放横着的小方块的方案数目（也即当我们将横着的小方块固定之后那么竖着的小方块直接填进去就可以了），如何判断当前的方案是否合法？我们只需判断所有剩余的位置是否可以填充竖着的小方块，可以按列来看，判断每一列内部所有连续的位置是否有偶数个，并且判断当前放置的横着的小方块是否与上一列放置的小方块发生冲突（为什么判断相邻两列的状态呢？其实只有上一列状态对当前这一列的状态才是有影响的==>放置的小方块是1 \* 2的）。我们可以定义一个二维数组，其中dp\[i\]\[j\]表示已经将前i列放好，第i列伸出到第i + 1列状态为j的所有方案，本质上是一列一列地填，每一列先放横着的小方块，然后横着的小方块固定之后那么竖着的小方块就固定了，塞进去即可。我们可以先预处理一下所有合法的状态，主要分为两个预处理，第一个预处理是记录下所有每一列连续的0的数目都是偶数个的合法状态（使用st数组来记录）；第二个预处理是记录下当前第t列状态为j的情况下，上一列t - 1列状态为j'的合法状态（使用state数组来记录，可以借助于st数组来判断当前相邻两列的状态是否发生冲突，因为有可能第t列伸出去了，第t - 1列也伸出去了导致了重合的问题），也即我们需要从上一个合法状态转移到当前的合法状态（哪些状态可以相互转移），根据状态定义可以知道最终dp\[m\]\[0\]就是答案，状态表示和状态计算可以参照下图：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_14_color_FFFFFF_t_70_g_se_x_16][]

**3. 代码如下：**

**python：**

if __name__ == '__main__':
        # 状态压缩dp
        while True:
            n, m = map(int, input().split())
            # 当n和m都等于0的时候就结束了
            if n == 0 and m == 0: break
            dp = [[0] * ((1 << n) + 1) for i in range(m + 1)]
            # st用来判断同一列中必须存在偶数个1的状态
            st = [0] * (1 << n)
            state = [list() for i in range((1 << n) + 1)]
            # 需要两步的预处理
            # 预处理一, 先计算出每一列对应的状态是否合法, 判断每一列空的位置是否有偶数个
            for i in range(1 << n):
                # count记录当前连续的0的个数
                count, is_valid = 0, 1
                for j in range(n):
                    # 当前状态为i对应的二进制数字的第j位是否是1
                    if i >> j & 1:
                        if count & 1:
                            is_valid = 0
                            break
                        # 清零, 当为偶数个的时候不清零其实也不影响
                        count = 0
                    # 连续的0的个数加1
                    else: count += 1
                # 最后判断最后那一段连续的1是否合法
                if count & 1: is_valid = 0
                st[i] = is_valid
            # 预处理二, 判断相邻的两列的状态是否合法, 这样在后面枚举当前状态的时候可以判断出当前状态这一列的状态是否和上一列的状态存在冲突
            for i in range(1 << n):
                # state[i].clear()
                for j in range(1 << n):
                    # 当前这一列的状态i与上一列的状态j中同一行没有交集才合法, 也即i & j = 0, 因为当两列同时伸出来的时候就重合了所以是不合法的, 并且需要满足st[i | j] = 1也即两个状态空的位置都是对应的两列都是有偶数个0的这样才可以放置竖着的方块
                    if i & j == 0 and st[i | j]:
                        # 当前这一列状态为i, 上一列的状态为j而且i和j都不冲突的合法方案
                        state[i].append(j)
            # 第0列其实是不存在的可以看成是第0列的方块是全部竖着放置的, 没有向第1列伸出来属于一种合法方案
            dp[0][0] = 1
            for i in range(1, m + 1):
                # 枚举当前状态为j
                for j in range(1 << n):
                    # 因为经过了预处理所以可以枚举上一列的状态k与当前的状态j没有冲突的合法方案
                    for k in state[j]:
                        dp[i][j] += dp[i - 1][k]
            print(dp[m][0])

**c++：**

#include<bits/stdc++.h>
    using namespace std;
    const int N=12, M = 1<< N;  
    
    long long f[N][M];
    bool st[M]; 
    vector<vector<int>> state(M); 
    int m, n;
    
    int main(){
        while(cin>>n>>m, n||m){ 
            for(int i=0; i< 1<<n; i++){
                int cnt =0;
                bool isValid = true; 
                for(int j=0;j<n;j++){
                     if( i>>j &1){ 
                        if(cnt &1) { 
                            isValid =false;break;
                        } 
                        cnt=0; 
                     }
                     else cnt++; 
                }
                if(cnt &1)  isValid =false; 
    
                st[i]  = isValid; 
            }
            for(int j=0;j< 1<<n;j++){ 
                state[j].clear(); 
                for(int k=0;k< 1<<n;k++){ 
                    if((j&k )==0 && st[ j| k] ) 
                        state[j].push_back(k);  
                }
    
            }
            memset(f,0,sizeof f);  
            f[0][0]=1 ;
            for(int i=1;i<= m;i++){ 
                for(int j=0; j< 1<<n; j++){  
                    for( auto k : state[j])   
                        f[i][j] += f[i-1][k]; 
                }
            }
            cout<< f[m][0]<<endl;
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/aafe3ebbffe54518a8b33eed85fb14db.png
[https_www.acwing.com_problem_content_description_293]: https://www.acwing.com/problem/content/description/293/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_14_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/20d7f50920f3479089dd16a61eb53556.png