AcWing291. 蒙德里安的梦想

题目描述

AcWing291. 蒙德里安的梦想

求把 N×M
的棋盘分割成若干个 1×2
的长方形，有多少种方案。

例如当 N=2，M=4 时，共有 5种方案。当 N=2，M=3 时，共有 3 种方案。
输入格式
输入包含多组测试用例。
每组测试用例占一行，包含两个整数 N和 M。
当输入用例 N=0，M=0
时，表示输入终止，且该用例无需处理。
数据范围
1 <= N , M <= 11 从数据范围也可以看出来用状态dp
输入样例

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

题目分析

其中只需要记住第i层的状态可以有i - 1层状态转移过来而第i - 1层的合法状态需要第i - 2层伸多来的和第i - 1层伸到第i层的状态剩下的空格是偶数个连续的0，并且第i - 2层伸过来的不冲突

代码

因为有多组测试数据为了降低代码的时间复杂度，可以先预处理出一个状态是否满足有偶数个连续的0，在此基础上在看满足不冲突的情况下i的上一项会是什么状态，就减少了每次循环判断的重复判断了

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

using namespace std;
typedef long long LL;
const int N = 12, M = 1 << N;

LL dp[N][M];
vector<vector<int> > state(M);// 表示这个状态满足是前一个状态可以为哪些
bool st[M];//用十进制表示时的是否满足有偶数个0

int main()
{
    int n, m;

    while (cin >> n >> m && (n || m))
    {
        for (int i = 0; i < (1 << n); i ++ )// 从00000(n个)遍历到最大的11111(n个)看有哪些状态有偶数个连续的0
        {
            int cnt = 0;
            bool is_Valid = true;
            
            for (int j = 0; j < n; j ++)
            {
                if ((i >> j) & 1) {// 当这个数是奇数时查看前面是否有偶数个0
                    if (cnt & 1){// 奇数个不合法
                        is_Valid = false; break;
                    }
                    cnt = 0;
                }
                else cnt ++;// 是偶数时加一个
            }
            if (cnt & 1) is_Valid = false;
            st[i] = is_Valid;
        }    
        // 预处理出哪些状态是不合法的
        // 在已经筛除一些状态后预处理出第i - 1 与第i行发生冲突的状态
        for (int i = 0; i < (1 << n); i ++)
        {
            state[i].clear();
            //i 表示第i行为这个状态时 将满足既不放置冲突又不存在奇数个零的合法状态(i - 1)这样的i加入可行方案
            for (int j = 0; j < (1 << n); j ++)
            {
                if((i & j) == 0 && st[i | j])// st[i | j] 表示i 这一行伸到下一行和i - 1行伸到i这一行的方块放完剩下的空方块状态
                    state[i].push_back(j);
            }
        }
        memset(dp, 0, sizeof dp);
        dp[0][0] = 1;// 初始化
        //进行dp
        for (int i = 1; i <= m; i ++)
            for (int j = 0; j < (1 << n); j ++)
                for (auto k : state[j])
                    dp[i][j] += dp[i - 1][k];
        
        printf("%lld\n", dp[m][0]);// 实际只有前0~n - 1行填充方块所以当最右边没有突出是就是答案
    }
    return 0;
}