ZeroJudge 解題筆記：d054. 11310 - DELIVERY DEBACLE

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


ZeroJudge 題目連結：d054. 11310 - DELIVERY DEBACLE

解題想法

這題考動態規畫，最難的地方是找遞迴關係式。$dp[n]$ 代表長度為 $n$ 時的排列方式數量，先列出前幾項：

1. $dp[0] = 1$，沒有任何的蛋糕，只有 1 種方式。
2. $dp[1] = 1$，只能放 2 個方形蛋糕，只有 1 種方式。
3. $dp[2] = 4 ＋ 1 ＝ 5$，用 1 個 L 形蛋糕及 1 個方形蛋糕佔據其中 4 格，再用 2 個方形蛋糕佔據剩下的 2 格，因為 L 形蛋糕的組合可以旋轉，有 4 種方式；也可以用 6 個方形蛋糕填滿 6 格，1 種方式；加起來共有 5 種方式。

$n = 3$ 開始會出現另一種排列方式，用 2 個 L 形蛋糕佔據其中 6 格，有以下 2 種方式

OOX     OXX
OXX     OOX

因此 $dp[3]$ 的組成有：

1. $dp[2] = 5$，用 2 個方形蛋糕佔據最後 2 格。
2. $4 \times dp[1] = 4 \times 1 = 4$，用 1 個 L 形蛋糕及 1 個方形蛋糕佔據最後 4 格，因為這個組合可以旋轉，要乘以 4。
3. $2 \times dp[0] = 2 \times 1 = 2$，用 2 個 L 形蛋糕佔據最後 6 格，這個組合有 2 種，要乘以 2。

$dp[3] = dp[2] + 4 \times dp[1] + 2 \times dp[0] = 5 + 4 \times 1 + 2 \times 1 = 11$ $dp[4]$ 的組成有：

1. $dp[3] = 11$，用 2 個方形蛋糕佔據最後 2 格。
2. $4 \times dp[2] = 4 \times 5 = 4$，用 1 個 L 形蛋糕及 1 個方形蛋糕佔據最後 4 格，因為這個組合可以旋轉，要乘以 4。
3. $2 \times dp[1] = 2 \times 1 = 2$，用 2 個 L 形蛋糕佔據最後 6 格，這個組合有 2 種，要乘以 2。
4. $dp[4] = dp[3] + 4 \times dp[2] + 2 \times dp[1] = 11 + 4 \times 5 + 2 \times 1 = 35$

遞迴關係式為 $$ dp[n] = dp[n-1] + 4 \times dp[n-2] + 2 \times dp[n-3] $$

Python 程式碼

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

def solve():
    import sys

    # 建表，n = 0 ~ 40
    dp = [1]*41
    dp[2] = 5
    for i in range(3, 41):
        dp[i] = dp[i-1] + 4*dp[i-2] + 2*dp[i-3]
    # 讀取資料並查表找答案
    result = []
    data = sys.stdin.read().split()
    ptr = 1
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        result.append(f"{dp[n]:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

C++ 程式碼

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

#include <cstdio>
typedef long long LL;

int main() {
    LL dp[41];
    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 5;
    for(int i=3; i<=40; i++) {
        dp[i] = dp[i-1] + 4*dp[i-2] + 2*dp[i-3];
    }
    int t; scanf("%d", &t);
    for(int i=0; i<t; i++) {
        int n; scanf("%d", &n);
        printf("%lld\n", dp[n]);
    }
    return 0;
}