ZeroJudge 解題筆記：a388. 00580 - Critical Mass

作者：王一哲
日期：2025年12月28日


ZeroJudge 題目連結：a388. 00580 - Critical Mass

解題想法

這題考動態規劃，定義 3 個串列

1. $dp0 = [0]*(1+n)$ # L 結尾，0 到 n 桶安全的放置組合數
2. $dp1 = [0]*(1+n)$ # U 結尾，0 到 n 桶安全的放置組合數
3. $dp2 = [0]*(1+n)$ # UU 結尾，0 到 n 桶安全的放置組合數

基礎狀態為只有 1 桶，1 種安全的組合 $dp0[1] = dp1[1] = 1$ 第 $2$ 到 $n$ 桶的狀態轉移關係為

1. dp0[i] = dp0[i-1] + dp1[i-1] + dp2[i-1]$ # 第 i 桶是 L，不管第 i-1 桶是 L 或 U 都是安全的
2. $dp1[i] = dp0[i-1]$ # 第 i 桶是 U，第 i-1 是 L
3. $dp2[i] = dp1[i-1]$ # 第 i 及 i -1 桶是 U

最後的答案為 $dp0[n] + dp1[n] + dp2[n]$

Python 程式碼

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

import sys

def solve(n):
    dp0 = [0]*(1+n)  # L 結尾，0 到 n 桶安全的放置組合數
    dp1 = [0]*(1+n)  # U 結尾，0 到 n 桶安全的放置組合數
    dp2 = [0]*(1+n)  # UU 結尾，0 到 n 桶安全的放置組合數
    dp0[1] = dp1[1] = 1  # 只有 1 桶，1 種安全的組合
    for i in range(2, n+1):  # 處理 2 到 n 桶
        dp0[i] = dp0[i-1] + dp1[i-1] + dp2[i-1]  # 第 i 桶是 L，不管第 i-1 桶是 L 或 U 都是安全的
        dp1[i] = dp0[i-1]  # 第 i 桶是 U，第 i-1 是 L
        dp2[i] = dp1[i-1]  # 第 i 及 i -1 桶是 U
    safe = dp0[n] + dp1[n] + dp2[n]  # 共 n 桶的安全放置組合數
    return (1 << n) - safe  # 可能的組合為 2**n，扣掉 safe 為不安全的組合數

for line in sys.stdin:
    n = int(line)
    if n == 0: continue
    print(solve(n))

C++ 程式碼

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

#include <cstdio>

int solve(int n) {
    int dp0[1+n] = {0}, dp1[1+n] = {0}, dp2[1+n] = {0};  // L 結尾、U 結尾、UU 結尾，0 到 n 桶安全的放置組合數
    dp0[1] = 1; dp1[1] = 1;  // 只有 1 桶，1 種安全的組合
    for(int i=2; i<=n; i++) {  // 處理 2 到 n 桶
        dp0[i] = dp0[i-1] + dp1[i-1] + dp2[i-1];  // 第 i 桶是 L，不管第 i-1 桶是 L 或 U 都是安全的
        dp1[i] = dp0[i-1];  // 第 i 桶是 U，第 i-1 是 L
        dp2[i] = dp1[i-1];  // 第 i 及 i -1 桶是 U
    }
    int safe = dp0[n] + dp1[n] + dp2[n];  // 共 n 桶的安全放置組合數
    return (1 << n) - safe;  // 可能的組合為 2**n，扣掉 safe 為不安全的組合數
}

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