解题报告：P8350 Mondriaans Dream

发表于 分类于

题意

给定一个 n×mn \times m 大小的长方形（1≤n,m≤111 \le n, m \le 11），求使用 1×21 \times 2 大小的长方形铺满它有多少种方案

思路

显然本题可以使用状态压缩 dp 解决

设计状态 dpi,jdp_{i, j} 表示放到第 ii 行，且第 ii 行状态为 jj 的情况下的答案

jj 用二进制表示第 kk 个格子是否是竖着铺且靠上的那个格子

考虑转移

如果当前行状态 pp 与上一行状态 qq 取与运算结尾不为 00，那么显然 p,qp, q 无法转移，因为 p,qp, q 存在同一列的两个格子都是竖着铺且靠上的那个格子

同时，p,qp, q 取或运算的结果意味着在当前行是被 1×21 \times 2（即竖着放）的长方形覆盖的，那么剩余的格子就是被横着放的长方形覆盖的

由于是横着放的，那么其长度必定为偶数，否则就不合法

由此可以得到判断 p,qp, q 直接转移合不合法的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool check(int x, int y)
{
    if ((x & y) != 0)
    {
        return false;
    }
    int tmp = (x | y) | (1 << m), last = -1, now = 0;
    while (tmp)
    {
        if ((tmp & 1) == 1)
        {
            if (((now - last - 1) & 1) != 0)
            {
                return false;
            }
            last = now;
        }
        tmp = tmp >> 1, now++;
    }
    return true;
}

注意在判断时要特别判断最后一段 00 的长度是否为偶数，不能漏判

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
namespace solution
{
    typedef long long LL;
    const int MAXN = 12 + 5;
    const int MAX2N = (1 << 12) + 5;
    LL n, m;
    LL dp[MAXN][MAX2N];
    bool check(int x, int y)
    {
        if ((x & y) != 0)
        {
            return false;
        }
        int tmp = (x | y) | (1 << m), last = -1, now = 0;
        while (tmp)
        {
            if ((tmp & 1) == 1)
            {
                if (((now - last - 1) & 1) != 0)
                {
                    return false;
                }
                last = now;
            }
            tmp = tmp >> 1, now++;
        }
        return true;
    }
    int main()
    {
        while (scanf("%lld%lld", &n, &m) != EOF && n != 0 && m != 0)
        {
            std::memset(dp, 0, sizeof(dp));
            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 (check(j, k))
                        {
                            dp[i][j] += dp[i - 1][k];
                        }
                    }
                }
            }
            printf("%lld\n", dp[n][0]);
        }
        return 0;
    }
}
int main()
{
    solution::main();
    return 0;
}