[AcWing], 蒙德里安的梦想

蒙德里安的梦想

  • 题目来源
  • 问题分析
    • 预处理合法的摆放方式
    • 动态规划
      • 初始化状态集
    • 结果
  • 完整代码

题目来源

https://www.acwing.com/problem/content/description/293/

[AcWing], 蒙德里安的梦想_第1张图片

问题分析

就是将一个n * m的二维矩阵,分成若干个1 * 2的方格,有多少种分配方式(完全分配)

可以对放置的方式进行模拟,先放置横着的1* 2方格,再放置竖着的2 * 1方格。那么摆放的小方格方案数 等价于 横着摆放的小方格方案数,因为当横着合法摆放的方格确定后,竖着摆放的方式就已经确定了,直接内嵌。

他的数据范围为1~11,暗示可以使用二进制来进行操作,状态压缩。那么我们选择对每一列的状态用一个二进制进行表示,当当前行所在的bit为0时,表示该位置没有放置;bit为1时,表示当前位置已经进行了放置。

[AcWing], 蒙德里安的梦想_第2张图片

列号 状态表示
0 0001
1 1001
2 1010
3 0010

所使用的变量
[AcWing], 蒙德里安的梦想_第3张图片

预处理合法的摆放方式

所以,我们在判断横着摆放方格的时候,就需要提前判断合法的摆放方式,防止竖着的方格放完后,不能完全铺满整个矩阵。
[AcWing], 蒙德里安的梦想_第4张图片
那么预处理的方法就是,对于每一种状态(二进制),然后依次遍历每一行,在遍历的途中需要记录的就是连续的没有放置的方格数(连续的0),当出现连续的0位奇数个时,表示该列的这种状态是不合法的。

[AcWing], 蒙德里安的梦想_第5张图片

动态规划

在动态规划中,我们从每一列开始遍历,然后从0 ~ 2^n依次遍历每一个状态。对于每一个j状态,我们需要找到一个他可以和哪个状态进行转换。

[AcWing], 蒙德里安的梦想_第6张图片
那么对于当前列在遍历时的状态,我们需要知道这个状态可以在前面的哪一个状态的情况后插入。如果前面当前行i-1是1,表示现在这一行i1*2方格的后半段,所以对于当前状态是不能插入的。

在判断当前状态是否合法时,可以使用 &来操作,如果结果为0,表示没有冲突。

除此之外,之前还做了一次预处理,判断当前状态是否合法。那么这个合法的状态就需要使用|来进行操作。
[AcWing], 蒙德里安的梦想_第7张图片

这样会出现一个小问题,就是这样问题的时间复杂度为O( 11 * 2^n * 2^n ),那么对于最坏的情况下,结果为 11 * 2^11 * 2^11 近似于 5 * 10^7,这是一个临界点,在超时的边缘徘徊。

(i & j) == 0 && st[i | j] 这两个条件换个位置后,就会超时)

[AcWing], 蒙德里安的梦想_第8张图片

所以我们可以将找状态集的过程提取出来,减少在三重循环中的判断次数。

初始化状态集

将结果保存在一个vector的可变数组中
[AcWing], 蒙德里安的梦想_第9张图片

结果

棋盘一共有0 ~ m-1列

  • f[i][j]表示 前i-1列的方案数已经确定,从i-1列伸出,并且第i列的状态是j的所有方案数
  • f[m][0]表示 前m-1列的方案数已经确定,从m-1列伸出,并且第m列的状态是0的所有方案数

也就是m列不放小方格,前m-1列已经完全摆放好并且不伸出来的状态
[AcWing], 蒙德里安的梦想_第10张图片

完整代码

#include 
#include 
#include 
#include 

using namespace std;
typedef long long ll;

const int N = 12, M = 1 << N; // 1-11 列,2^11 个状态
ll f[N][M];             // f[i][j] 从第i-1列伸出,到i列,状态为j,  j 的二进制位为1表示当前行放置方格,为0表示不放置
vector<int> state[M];   // 每一种状态,对应可以放置的状态
bool st[M];             // 是否可以成功转移,j 状态放置 k状态后 是否合法

int n, m;

int main() {
     
    while(cin >> n >> m, n || m) {
     
        
        // 初始化
        for(int i = 0; i < (1 << n); i ++) {
     
            int cnt = 0;    // 前面连续0的数量
            bool is_valid = true;
            
            for(int j = 0; j < n; j ++) {
     
                if((i >> j) & 1) {
           // 1 放置
                    if(cnt & 1) {
            // 前面连续0位奇数,不合法
                        is_valid = false;
                        break;
                    }
                    cnt = 0;
                } else {
         // 0 不放置,连续0 + 1
                    cnt++;
                }
            }
            
            if(cnt & 1) is_valid = false;   // 余下0位奇数个,不合法
            st[i] = is_valid;
        }
        
        for(int i = 0; i < (1 << n); i ++) {
     
            state[i].clear();
            for(int j = 0; j < (1 << n); j ++) 
                if((i & j) == 0 && st[i | j])   state[i].push_back(j);  // 对于状态i来说,可以插入的状态为j
        }
        
        memset(f,0x00,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;
    }
    return 0;
}

你可能感兴趣的