递推算法与大数处理

### 问题描述
PHT学校的校长PigHeader希望所有学生按照一定的规则排队。具体规则为：不允许单个女生单独站立，即要么没有女生，要么至少有两个女生相邻站立。给定n个孩子（1 <= n <= 1000），求满足条件的队伍排列总数。

#### 输入格式
输入包含多组数据，每组数据一行，包含一个整数n，表示孩子的数量。输入以EOF结束。

#### 输出格式
对于每组数据，输出一行，包含一个整数，表示满足条件的队伍排列总数。

#### 示例

- **输入**
```
1
2
3
```
- **输出**
```
1
2
4
```

### 解决方案
该问题可以通过递推公式来解决。根据题目要求，可以得出递推关系式：fn = fn-1 + fn-2 + fn-4。由于n的范围较大，直接计算可能会导致数值溢出，因此需要使用数组存储大数结果。

以下是C++代码实现：
```cpp
#include
#include
#include
#define MAXM 1001
#define MAXN 502
using namespace std;

int a[MAXM][MAXN];

int main() {
int n, i, j;
memset(a, 0, sizeof(a));
a[1][0] = 1; a[2][0] = 2; a[3][0] = 4; a[4][0] = 7;

for (i = 5; i for (j = 0; j a[i][j] += a[i - 1][j] + a[i - 2][j] + a[i - 4][j];
if (a[i][j] >= 10) {
a[i][j + 1] += a[i][j] / 10;
a[i][j] %= 10;
}
}
}

while (scanf("%d", &n) != EOF) {
for (i = 500; a[n][i] == 0; i--);
for (; i >= 0; i--) {
printf("%d", a[n][i]);
}
printf("\n");
}
return 0;
}
```