UVA 580：Critical Mass——DP 計算不安全棧序列數

問題

向棧中連續放入 n 個字符，每次可放 'U' 或 'L'。若出現連續三個 'U' 則不安全。求不安全序列總數（模無，直接輸出整數）。

解法一：DP 計算安全序列，總數減去

• dp[i][j]：前 i 步，結尾連續 j 個 'U' (j=0,1,2) 的安全序列數。
• 轉移：放 'L' → dp[i+1][0] += Σ dp[i][*]；放 'U' → dp[i+1][j+1] = dp[i][j]（j<2）。
• 安全總數 = Σ dp[n][j]，答案 = 2^n - 安全總數。

ll dp[40][3];
ll solve(int n){
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    for(int i=1;i<=n;++i){
        for(int j=0;j<3;++j) dp[i][0]+=dp[i-1][j];
        for(int j=1;j<=2;++j) dp[i][j]=dp[i-1][j-1];
    }
    ll safe=0; for(int j=0;j<3;++j) safe+=dp[n][j];
    return (1LL<
解法二：直接 DP 於以 L 結尾的序列
dp[i] 表示長度 i 以 'L' 結尾的安全序列數。dp[i]=dp[i-1]+dp[i-2]+dp[i-3]（最後 1~3 個 'U' 後接 'L'）。安全總數 = dp[n]+dp[n-1]+dp[n-2]（允許結尾 0~2 個 'U'）。答案同前。
ll dp[40];
ll solve2(int n){
    memset(dp,0,sizeof(dp));
    dp[0]=dp[1]=1;
    for(int i=2;i<=n;++i)
        for(int j=1;j<=3 && j<=i;++j) dp[i]+=dp[i-j];
    ll safe=0;
    for(int i=0;i<=2 && i<=n;++i) safe+=dp[n-i];
    return (1LL<
複雜度
O(n)，n≤30 時 2^n 可用 64 位整數存儲。