#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; }

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

递推做法 人数/排法 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; }