前置： a[n]储存第n个人的可能性 从最后一个人思考： 如果最后一个人是m，则无所谓前面的情况，故可能性为a[n-1]; 如果最后一个人是f，则前面必须是f，故可能性为a[n-2]; 特殊情况：当结尾是ff的时候，会救活一种特殊可能，也就是以mf为结尾的可能，组成后四个mfff。所以新增可能性a[n-4] 注：mffm这种情况下，mff是合理的所以已经被包含在a[n-1]。

#include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; int a[31] = {0,1,2,4,7,12}; for (int i=5;i<=n;i++) a[i] = a[i-1]+a[i-2]+a[i-4]; cout<<a[n]; return 0; }

递推做法 人数/排法 1 1 2 2 3 4 4 7 5 12 6 21 由此可得 递归边界为4 递归式为a[i-1]+a[i-2]+a[i-4];

#include<bits/stdc++.h> using namespace std; int p[100005]; int main(){ int n; cin >> n; p[1] = 1; p[2] = 2; p[3] = 4; p[4] = 7; p[5] = 12; for(int i = 6;i <= n;i++) p[i] = p[i-1] + p[i-2] + p[i-4]; cout << p[n]; return 0; }

题意：用 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）