【状压DP】蒙德里安的梦想

题目

291. 蒙德里安的梦想

---

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

例如当 $N=2，M=4$ 时，共有 $5$ 种方案。当 $N=2，M=3$ 时，共有 $3$ 种方案。

如下图所示：

输入格式

输入包含多组测试用例。

每组测试用例占一行，包含两个整数 $N$ 和 $M$ 。

当输入用例 $N=0，M=0$ 时，表示输入终止，且该用例无需处理。

输出格式

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

数据范围

$1 \le N,M \le 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

解题

方法一：动态规划

思路

先横着放小方块，再竖着放，此时发现所有摆放方案的个数等于按照列来横着放置小方块的合法方案数。

如何判断当前方案是否合法？

• 不能与上一列冲突，也就是两列的状态表示做与运算必须等于 $0$ 。
• 所有剩余位置必须能填充满竖着的小方块，也就是：该列中所有连续为空的格子数必须为偶数。

思维过程：

如上图的状态表示为：$f(i, 110011_{(2)})$。

动态规划：

• 状态定义：$dp[i][j]$ 表示已经摆完前 $i-1$ 列，且从 $i-1$ 列伸出来横着的方格状态为 $j$ （状态压缩）的方案数。

• 状态转移方程：$dp[i][j] = \sum{dp[i - 1][k]}$ （$k$ 状态合法）。

• 初始状态：$dp[0][0]$ 为一种合法的方案（空棋盘），所以：$dp[0][0] = 1$。

注意：每次测试有多数组数据，每次都要进行初始化。

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int N = 12, M = 1 << N;
    static long[][] dp = new long[N][M];
    static List<Integer>[] states = (ArrayList<Integer>[]) new ArrayList[M];
    static boolean[] isValids = new boolean[M];
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        while (true) {
            in.nextToken();
            int n = (int) in.nval;
            in.nextToken();
            int m = (int) in.nval;
            if (n == 0 && m == 0) break;
            int o = 1 << n;
            // 预处理合法的状态
            for (int i = 0; i < o; ++i) {
                int cnt = 0;
                boolean isValid = true;
                for (int j = 0; j < n; ++j) {
                    if ((i & (1 << j)) != 0) {
                        if ((cnt & 1) != 0) {
                            isValid = false;
                            break;
                        }
                        cnt = 0;
                    } else ++cnt;
                }
                if ((cnt & 1) != 0) isValid = false;
                isValids[i] = isValid;
            }
            // 预处理从一个状态可以转移到的合法的状态
            for (int i = 0; i < o; ++i) {
                if (states[i] == null) states[i] = new ArrayList<>();
                else states[i].clear();
                for (int j = 0; j < o; ++j) {
                    if ((i & j) == 0 && isValids[i | j]) {
                        states[i].add(j);
                    }
                }
            }
            // 初始化dp数组
            for (int i = 0; i <= m; ++i) {
                for (int j = 0; j < o; ++j) dp[i][j] = 0;
            }
            dp[0][0] = 1;
            // 动态规划
            for (int i = 1; i <= m; ++i) {
                for (int j = 0; j < o; ++j) {
                    for (int s : states[j]) dp[i][j] += dp[i - 1][s];
                }
            }
            System.out.println(dp[m][0]);
        }
    }
}