AcWing 291.蒙德里安的梦想

标签：http   一个   include   bool   const   typedef   mem   https   表示   

题目：蒙德里安的梦想

链接:(蒙德里安的梦想)[https://www.acwing.com/problem/content/293/]

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

分析：
1.当把所有横着的长方形放置好后，那么竖着的长方形的放置方法是唯一的
2.f[i, j]表示放置第i列时，第i列的状态是j的所有方案，j表示从第i - 1列伸出方块到第i列的状态
3.竖着的空着方块是用来放置1 * 2的长方形的，因此需要连续偶数个空方块，我们可以预处理出来是否能放置
4.如何正确地转移？首先不能产生冲突，f[i - 1, k]表示放置第i - 1列时，k是从i - 2列伸出来到i - 1列的方块
所以为了避免产生冲突，要放置长度为2的长方形，k & j必须为0，某一列的某一行只能放置一个方块
5.一列不能连续存在奇数个0，为了用来摆放竖着的长方形

#include 
#include 
#include 

using namespace std;

const int n = 12;
const int m = 1 > j & 1) {//判断之前已经累计好的0个数为奇数
                    if (cnt & 1)
                        st[i] = false;//为奇数，设置为false
                    cnt = 0;//重新累计0的个数
                }
                else {
                    ++cnt;//没碰到1，就累计0的个数
                }               
            }
            if (cnt & 1)
                st[i] = false;//如果最后的是连续的0，没有碰到1，就需要再判断一下
        }
        
        memset(f, 0, sizeof f);
        f[0][0] = 1;
        for (int i = 1; i 

AcWing 291.蒙德里安的梦想

标签：http   一个   include   bool   const   typedef   mem   https   表示   

原文地址：https://www.cnblogs.com/pixel-Teee/p/11965634.html