T02663: 完美覆盖

dp, http://cs101.openjudge.cn/practice/02663/

一张普通的国际象棋棋盘，它被分成 8 乘 8 (8 行 8 列) 的 64 个方格。设有形状一样的多米诺牌，每张牌恰好覆盖棋盘上相邻的两个方格，即一张多米诺牌是一张 1 行 2 列或者 2 行 1 列的牌。那么，是否能够把 32 张多米诺牌摆放到棋盘上，使得任何两张多米诺牌均不重叠，每张多米诺牌覆盖两个方格，并且棋盘上所有的方格都被覆盖住？我们把这样一种排列称为棋盘被多米诺牌完美覆盖。这是一个简单的排列问题，同学们能够很快构造出许多不同的完美覆盖。但是，计算不同的完美覆盖的总数就不是一件容易的事情了。不过，同学们发挥自己的聪明才智，还是有可能做到的。现在我们通过计算机编程对 3 乘 n 棋盘的不同的完美覆盖的总数进行计算。

任务对 3 乘 n 棋盘的不同的完美覆盖的总数进行计算。

输入

一次输入可能包含多行，每一行分别给出不同的 n 值 ( 即 3 乘 n 棋盘的列数 )。当输入 -1 的时候结束。

n 的值最大不超过 30.

输出

针对每一行的 n 值，输出 3 乘 n 棋盘的不同的完美覆盖的总数。

样例输入

样例输出

3
153
2131

参考：https://segmentfault.com/a/1190000013500389?utm_source=tag-newest

思路

首先，列数n肯定要是偶数，因为n*3/2得是整数。

然后我们来想递推公式。因为n是偶数，所以n-1, n-3这种奇数列，必然无法完全覆盖。我们不考虑。

首先，f(n)可以由f(n-2)推得，则剩下的两列还有三种方法。

所以f(n)至少要等于3 * f(n-2).

那么f(n)可不可以由f(n-4)推得呢？对于剩下的4列，如果是上图中任两种情况的组合，那它实际上就还是f(n-2)中的情况，因此重合了。必须要找到一种无法被拆成完美2列的4列图形。也就是说，单看两列时是参差不齐的。这时才不与f(n-2)的情形重合。

那么有没有这种图形呢？见下图：

同理，6列的类似图形是这样：

可以看出这种图形的特点：为了避免能被拆成2列的图形，在内部要有参差不齐。方法就是一行平躺，然后其余两行两边竖着放，中间横着放。尝试几次后就会发现只有这种方案。

因为平躺的那行可以在上面也可以在下面，因此无法分割的4列、6列、8列……的排列方法都是有两种。

由此，我们便能写出递推公式：

javascript

f(2) = 3,
f(4) = 3 * f(2) + 2 * 1,
f(6) = 3 * f(4) + 2 * (f(2) + 1), // 后半部分是不可拆分4列和不可拆分6列的形状数量。
f(n) = 3 * f(n-2) + 2 * (f(n-4) + f(n-6) + ... + f(2) + 1)
     = f(n-2) + 2 * (f(n-2) + f(n-4) + ... + f(2) + 1)

优化

上面程序已经能通过。但递归写法会造成重复计算。可以用一个数组保存计算结果。另外既然答案要求f(0) = 1，则可以将递推公式写成：

undefined

f(n) = 3 * f(n-2) + 2 * (f(n-4) + f(n-6) + ... + f(0))

将f(n)与f(n-2)相减可得

undefined

f(n) = 4 * f(n-2) - f(n-4)

这下就简单多了。

python

import sys

def compute_tilings(max_n):
    # 预计算 f[0..max_n]
    f = [0] * (max_n + 1)
    f[0] = 1
    if max_n >= 2:
        f[2] = 3
    # 只对偶数 n 进行递推
    for n in range(4, max_n + 1, 2):
        f[n] = 4 * f[n-2] - f[n-4]
    return f

def main():
    # 读入所有的 n 值
    ns = []
    for line in sys.stdin:
        line = line.strip()
        if not line:
            continue
        n = int(line)
        if n == -1:
            break
        ns.append(n)
    if not ns:
        return

    max_n = max(ns)
    # 最大不超过 30，且偶数部分可预计算
    dp = compute_tilings(max_n if max_n % 2 == 0 else max_n-1)

    # 输出结果
    for n in ns:
        # 奇数列无法覆盖
        if n % 2 == 1:
            print(0)
        else:
            print(dp[n])

if __name__ == "__main__":
    main()

T02663: 完美覆盖 ​

T02663: 完美覆盖