Time Limit: 3000/3000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
有一天上体育课，老师让所有的学生排成一行，同时要求女生不能单独的站在队列中，也就说必须有2个以上的女生站在一起。举例来说，假如有4个学生，那么可能的排列方式为FFFF, FFFM, MFFF, FFMM, MFFM, MMFF, MMMM（其中F表示女生，M表示男生），4个学生有以上的7种组合。请编写程序，计算n个学生的符合以上要求的排队方式数量。（1<=n<=1000）
输入正整数n，其中1<=n<=1000
输出符合要求的数量，其中当n为1000时，返回的值非常大，请注意处理这种大数问题。
4
5
10
20
7
12
200
55405
#include <stdio.h> int result[1005][105]={0}; void init2(int n); void init(){ int i; result[1][1] = 1; result[2][1] = 2; result[3][1] = 4; result[4][1] = 7; for(i = 5;i<1001;i++) { init2(i); } } int main() { int n,i; init(); while(scanf("%d",&n)!=EOF) { //找到第一个不为零的 for(i = 100;i > 0&& result[n][i]==0;i--); //输出结果 printf("%d",result[n][i]); --i; for(;i>0;--i) { printf("%04d",result[n][i]); } printf("\n"); } return 0; } void init2(int n) { int dddddd=0,i; for(i = 1;i<101;i++) { dddddd += result[n-1][i] + result[n-2][i] + result[n-4][i]; result[n][i] = dddddd%10000; dddddd /= 10000; } while(dddddd) { result[n][i++] = dddddd%10000; dddddd /= 10000; } }
原文：http://www.cnblogs.com/stonehat/p/4875887.html