题目链接：uva 580 - Critical Mass

题目大意：给定一个栈，向栈里连续添加n次，每次可以添加U或者L，如果出现连续三个U则为不安全，问有多少种不安全的可能。

解题思路：先求出安全的，用总数减去安全的即为答案。
dp[i][j]表示以第i个位置结尾时，有末尾有j个连续的U。
还有一种解法，dp[i]表示第i个位置以L结尾的总数，dp[i] = dp[i-1] + dp[i-2] + dp[i-3];

解法一：

#include 
   
     #include 
    
      typedef long long ll; 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 ans = 0; for (int i = 0; i < 3; i++) ans += dp[n][i]; return (1LL<
     






    
   

#include 
    
      #include 
     
       #include 
      
        using namespace std; typedef long long ll; ll dp[40]; ll solve(int n) { memset(dp, 0, sizeof(dp)); dp[0] = dp[1] = 1; for (int i = 2; i <= n; i++) { for (int j = 1; j <= min(3, i); j++) dp[i] += dp[i-j]; } ll ans = 0; for (int i = 0; i <= min(n, 2); i++) ans += dp[n-i]; return (1LL<