由于长宽都比较小,采用棋盘式状态压缩DP解决,此类任务一般是在棋盘内填各种形状的块,然后求方案数。

核心思想是:总方案数等于合法横向摆放小矩形方案数之和。下面的图形中,绿色为横向填充,黄色为纵向填充,图1是合法的,图2则是非法的。

图片说明

设状态矩阵为dp[i][j],其中i表示第i列,j表示横跨第i-1列和第i列的横向小矩阵的行号的二进制表示,如:

图片说明

同时,存在如下约束条件:

  • j&k == 0(设i-1列的状态为k)
  • 摆完第i列后,第i列中放置纵向小矩阵的连续空格数要为偶数个,因此j|k中不能存在连续奇数个空格,这个可以通过预处理获得

对于第二个约束条件,很多题解说的是考虑当第i列摆放完后,第i列中不能存在连续的奇数个空格,即j|k中不存在连续奇数个0,其中第i列中不能存在连续的奇数个空格其实是不对的,因为第i列中有些空格属于横向小矩阵的头,这些空格应该作为1来考虑

初始状态:dp[0][0]=1,状态转移公式:dp[i][j] = sum(dp[i-1][k]),其中0 <=k<= 1<<n(n为行数)

参考链接

代码如下:

//
// Created by jt on 2020/9/28.
// 蒙德里安的梦想:https://ac.nowcoder.com/acm/contest/1046/A
#include <iostream>
#include <cstring> // memset
using namespace std;

const int M = 12, N = 1 << M;
long long dp[M][N];
bool state[N]; // state[i]==true表示i中连续0的个数都为偶数

int main() {
    int m, n; // m为行数,n为列数
    while (cin >> m >> n, m && n) {
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < 1 << m; ++i) {
            state[i] = true; int cnt = 0;
            for (int j = 0; j < m; ++j) {
                // 注意&的优先级低于==
                if ((i >> j & 1) == 0) ++cnt;
                else {
                    if((cnt & 1) == 1) {state[i] = false; break; }
                    else cnt = 0;
                }
            }
            if ((cnt & 1) == 1) state[i] = false;
        }
        dp[0][0] = 1; // 初始状态
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < 1 << m; ++j) {
                for (int k = 0; k < 1 << m; ++k) {
                    // 满足两个约束条件
                    if ((state[j|k]) && ((j & k) == 0))
                        dp[i][j] += dp[i-1][k];
                }
            }
        }
        cout << dp[n][0] << endl; // 结果为第m+1列没有伸出小矩阵的情况
    }
}