递推问题实现起来很简单，但得到递推公式确实很麻烦，就像DP一样。
分析（部分出自HDU的PPT）：
设：F（n）表示n个人的合法队列，则：
按照最后一个人的性别分析，他要么是男，要么是女，所以可以分两大类讨论：
1、如果n个人的合法队列的最后一个人是男，则对前面n-1个人的队列没有任何限制，他只要站在最后即可，所以，这种情况一共有F（n-1）；
2、如果n个人的合法队列的最后一个人是女，则要求队列的第n-1个人务必也是女生，这就是说，限定了最后两个人必须都是女生，这又可以分两种情况：
（1）、如果队列的前n-2个人是合法的队列，则显然后面再加两个女生，也一定是合法的，这种情况有F（n-2）；
（2）难点在于，即使前面n-2个人不是合法的队列，加上两个女生也有可能是合法的，当然，这种长度为n-2的不合法队列，不合法的地方必须是尾巴，就是说，这里说的长度是n-2的不合法串的形式必须是"F（n-4）+男+女",这种情况一共有F（n-4）。
所以递推公式为F（n）=F（n-1）+F（n-2）+F（n-4）。
另外需要注意的是 这个递推式的数据范围到了1000,int甚至long long 都已经无法承载最大边界，所以我使用了前两天贴出的大数类。
[cpp]
#include<iostream>
#include<string>
#include<iomanip>
#include<algorithm>
using namespace std;
#define MAXN 9999
#define MAXSIZE 10
#define DLEN 4
class BigNum
{
private:
int a[500]; //可以控制大数的位数
int len; //大数长度
public:
BigNum（）{ len = 1;memset（a,0,sizeof（a））； } //构造函数
BigNum（const int）； //将一个int类型的变量转化为大数
BigNum（const char*）； //将一个字符串类型的变量转化为大数
BigNum（const BigNum &）； //拷贝构造函数
BigNum &operator=（const BigNum &）； //重载赋值运算符，大数之间进行赋值运算
friend istream& operator》（istream&, BigNum&）； //重载输入运算符
friend ostream& operator《（ostream&, BigNum&）； //重载输出运算符
BigNum operator+（const BigNum &） const; //重载加法运算符，两个大数之间的相加运算
BigNum operator-（const BigNum &） const; //重载减法运算符，两个大数之间的相减运算
BigNum operator*（const BigNum &） const; //重载乘法运算符，两个大数之间的相乘运算
BigNum operator/（const int &） const; //重载除法运算符，大数对一个整数进行相除运算
BigNum operator^（const int &） const; //大数的n次方运算
int operator%（const int &） const; //大数对一个int类型的变量进行取模运算
bool operator>（const BigNum & T）const; //大数和另一个大数的大小比较
bool operator>（const int & t）const; //大数和一个int类型的变量的大小比较
void print（）； //输出大数
};
BigNum::BigNum（const int b） //将一个int类型的变量转化为大数
{
int c,d = b;
len = 0;
memset（a,0,sizeof（a））；
while（d > MAXN）
{
c = d - （d / （MAXN + 1）） * （MAXN + 1）；
d = d / （MAXN + 1）；
a[len++] = c;
}
a[len++] = d;
}
BigNum::BigNum（const char*s） //将一个字符串类型的变量转化为大数
{
int t,k,index,l,i;
memset（a,0,sizeof（a））；
l=strlen（s）；
len=l/DLEN;
if（l%DLEN）
len++;
index=0;
for（i=l-1;i>=0;i-=DLEN）
{
t=0;
k=i-DLEN+1;
if（k<0）
k=0;
for（int j=k;j<=i;j++）
t=t*10+s[j]-'0';
a[index++]=t;
}
}
BigNum::BigNum（const BigNum & T） : len（T.len） //拷贝构造函数
{
int i;
memset（a,0,sizeof（a））；
for（i = 0 ; i < len ; i++）
a[i] = T.a[i];
}
BigNum & BigNum::operator=（const BigNum & n） //重载赋值运算符，大数之间进行赋值运算
{
int i;
len = n.len;
memset（a,0,sizeof（a））；
for（i = 0 ; i < len ; i++）
a[i] = n.a[i];
return *this;
}
istream& operator》（istream & in, BigNum & b） //重载输入运算符
{
char ch[MAXSIZE*4];
int i = -1;
in》ch;
int l=strlen（ch）；
int count=0,sum=0;
for（i=l-1;i>=0;）
{
sum = 0;
int t=1;
for（int j=0;j<4&&i>=0;j++,i--,t*=10）
{
sum+=（ch[i]-'0'）*t;
}
b.a[count]=sum;
count++;
}
b.len =count++;
return in;
}