題目鏈接：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<