题解【递推】

#include <bits/stdc++.h>
using namespace std;
long long dp[35][3];
// dp[i][0]: 长度为 i，末尾是 M，且队列合法
// dp[i][1]: 长度为 i，末尾是单个 G（孤立，不合法中间状态）
// dp[i][2]: 长度为 i，末尾是 ≥2 个连续 G，且队列合法
int main()
{
    int n;
    cin >> n;
    // 初始：长度为 1
    dp[1][0] = 1;   // "M"
    dp[1][1] = 1;   // "G"（孤立，作为中间状态）
    dp[1][2] = 0;   // 不可能
    for (int i = 2; i <= n; i++)
    {
        dp[i][0] = dp[i - 1][0] + dp[i - 1][2];   // 末尾放 M，前面必须合法
        dp[i][1] = dp[i - 1][0];                  // 末尾放单个 G，前面末尾必须是 M
        dp[i][2] = dp[i - 1][1] + dp[i - 1][2];   // 末尾放 G 与前面 G 配对
    }
    // 合法队列 = 末尾是 M + 末尾是 ≥2 个 G
    cout << dp[n][0] + dp[n][2];
    return 0;
}