T7:学生排队

题意：用 M 表示男孩，F 表示女孩。长度为 n 的队列中，女孩不能单独站。也就是：队列里任何一段连续的 F，长度不能等于 1（要么没有 F，要么每段 F 的长度都 ≥ 2）。

这类约束适合用 DP 按“结尾形态”分类。

---

状态定义

设 dp[i][state] 表示长度为 i 的队列方案数，其中：

• state = 0：结尾是 M，并且当前队列 合法
• state = 1：结尾是 单独的一个 F（…MF 或开头 F），此时队列 暂时不合法，必须再接一个 F 才能变合法
• state = 2：结尾是 连续 ≥ 2 个 F，并且当前队列 合法

最终答案只能是合法结束：

• dp[n][0] + dp[n][2]

---

转移方程（关键：单个 F 后不能接 M）

1. 结尾变成 M：

• 只能从合法状态接 M 来：从 state 0 或 state 2 接 M
• 不能从 state 1 接 M（否则会把那个单独的 F 固定下来，违反题意）

所以：

• dp[i][0] = dp[i-1][0] + dp[i-1][2]

2. 结尾变成“单个 F”（state 1）：

• 只能从结尾是 M 的合法状态接一个 F 来

所以：

• dp[i][1] = dp[i-1][0]

3. 结尾变成“连续 ≥2 个 F”（state 2）：

• 从 state 1 再接一个 F（把单个 F 补成一段长度 2）
• 或者从 state 2 继续接 F（保持 ≥2）

所以：

• dp[i][2] = dp[i-1][1] + dp[i-1][2]

---

初始化

把空队列看成合法且“结尾为 M”状态，方便统一转移：

• dp[0][0] = 1
• dp[0][1] = dp[0][2] = 0

---

复杂度

• 时间：O(n)
• 空间：O(n)（这里用数组写，n ≤ 30 很小）

---

C++ 代码（普通数组 + endl）

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    long long dp[35][3] = {0};
    dp[0][0] = 1; // 空队列：合法，视作结尾是 M

    for (int i = 1; i <= n; i++) {
        dp[i][0] = dp[i - 1][0] + dp[i - 1][2]; // 接 M
        dp[i][1] = dp[i - 1][0];                // 从结尾M接一个F，形成单个F
        dp[i][2] = dp[i - 1][1] + dp[i - 1][2]; // 单个F补成>=2 或 >=2继续接F
    }

    cout << dp[n][0] + dp[n][2] << endl;
    return 0;
}