UVA580 Critical Mass 【思维+DP】

为表示方便，设字符U为0，设字符L为1，题目转化为求长度为n的非法01串种类数（含连续三位000即为非法）

反向思维，可用DP维护长度为$i$的串的合法状态数，不难发现初始化为：

$dp[1]=2$

• (0, 1)

$dp[2]=4$

• (00, 01, 10, 11)

$dp[3]=7$

• (001, 010, 011, 100, 101, 110, 111)

转移方程为：

$dp[i]=dp[i-1]+dp[i-2]+dp[i-3]$

三个子项分别对应尾部追加$“1”,“10”,“100”$子串的情况，转移结果示例：

$dp[4]=13$

• 来自$dp[1]$的转移 (0100, 1100) 共2种
• 来自$dp[2]$的转移 (0010, 0110, 1010, 1110) 共4种
• 来自$dp[3]$的转移 (0011, 0101, 0111, 1001, 1011, 1101, 1111) 共7种

易自证编码互不冲突。

至此，问题可以通过全排列数减对应合法状态数得到非法状态数进行求解：

$ans[n]=2^n-dp[n]$

代码如下：

#include <iostream>
#include <cmath>
using namespace std;
const int maxn = 30 + 10;
int dp[maxn];   // number of valid 0-1 strings (substring 000 is illegal)
int main()
{
    int n;
    dp[1] = 2;  // 0, 1
    dp[2] = 4;  // 00, 01, 10, 11
    dp[3] = 7;  // 001, 010, 011, 100, 101, 110, 111
    
    for (int i = 4; i < maxn; i ++){
        dp[i] += dp[i-1];   // += 1
        dp[i] += dp[i-2];   // += 10
        dp[i] += dp[i-3];   // += 100
    }
    while (cin >> n && n){
        cout << (int)ceil(pow(2,n)) - dp[n] << endl;;
    }
    return 0;
}