侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-12-01 / 0 评论 / 0 点赞 / 229 阅读 / 879 字
温馨提示:
本文最后更新于 2022-12-01,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

291. 蒙德里安的梦想


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

例如当 N=2M=4N=2,M=4 时,共有 55 种方案。当 N=2M=3N=2,M=3 时,共有 33 种方案。

如下图所示:

2411_1.jpg

输入格式

输入包含多组测试用例。

每组测试用例占一行,包含两个整数 NNMM

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

输出格式

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

数据范围

1N,M111 \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

解题

方法一:动态规划

思路

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

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

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

思维过程:

image-20221201204603018

image-20221201205746058

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

动态规划:

  • 状态定义:dp[i][j]dp[i][j] 表示已经摆完前 i1i-1 列,且从 i1i-1 列伸出来横着的方格状态为 jj (状态压缩)的方案数。

  • 状态转移方程:dp[i][j]=dp[i1][k]dp[i][j] = \sum{dp[i - 1][k]}kk 状态合法)。

  • 初始状态:dp[0][0]dp[0][0] 为一种合法的方案(空棋盘),所以:dp[0][0]=1dp[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]);
        }
    }
}
0

评论区