ZeroJudge 解題筆記：b587. 10918 - Tri Tiling

作者：王一哲
日期：2026年1月19日


ZeroJudge 題目連結：b587. 10918 - Tri Tiling

解題想法

因為地板的尺寸為 $3 \times n$，要放入的地板磚尺寸為 $1 \times 2$，如果 $n$ 為奇數時無解。接下來列出 $n$ 的前幾項可能的拼法，例如 $n = 2$ 有 3 種

AA   AB   CC
BB   AB   AB
CC   CC   AB

如果以 $dp[n]$ 代表地板尺寸為 $3 \times n$ 的拼法數量，其中 $dp[0] = 1$，因為沒有放置地板算 1 種；$dp[2] = 3$，像是上面的例子；接下來推算 $n \geq 4$ 的狀況。 狀況1，如果最右側是完整的 $3 \times 2$，這個部分有 3 種拼法，左側的拼法為 $dp[n-2]$，因此 $dp[n] = 3 \times dp[n-2]$。 狀況2，如果最右側不是完整的 $3 \times 2$，先列出 $$ dp[n] = 3 \times dp[n-2] + 2 \times (dp[n-4] + dp[n-6] + \dots + dp[0]) $$ 再列出 $$ dp[n-2] = 3 \times dp[n-4] + 2 \times (dp[n-6] + dp[n-8] + \dots + dp[0]) $$ 將兩式相減 $$ dp[n] - dp[n-2] = 3 \times dp[n-2] - dp[n-4] $$ 移項後得到 $$ dp[n] = 4 \times dp[n-2] - dp[n-4] $$

Python 程式碼

使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

import sys

def solve(n):
    if n == 0: return 1
    if n == 2: return 3
    if n%2 == 1: return 0
    dp = [0]*(n+1)
    dp[0] = 1; dp[2] = 3
    for i in range(4, n+1, 2):
        dp[i] = 4*dp[i-2] - dp[i-4]
    return dp[n]

for line in sys.stdin:
    n = int(line)
    if n == -1: break
    print(solve(n))

C++ 程式碼

使用時間約為 2 ms，記憶體約為 96 kB，通過測試。

#include <cstdio>

int solve(int n) {
    if (n == 0) return 1;
    if (n == 2) return 3;
    if (n%2 == 1) return 0;
    int dp[n+1] = {0};
    dp[0] = 1; dp[2] = 3;
    for(int i=4; i<=n; i+=2) {
        dp[i] = 4*dp[i-2] - dp[i-4];
    }
    return dp[n];
}

int main() {
    int n;
    while(scanf("%d", &n) != EOF) {
        if (n == -1) break;
        printf("%d\n", solve(n));
    }
    return 0;
}