这个题目也是递推，但是比较有意思的是要涉及到高精度
递推式：f[i]=f[i-1]+f[i-2]+f[i-4]
思路：1、i-1个排好了，只能再加一个F，共f[i-1]种
2、i-2个排好了，a、可以加两个F；b、可以加两个M，但是两个F跟第一种冲突了，所以有f[i-2]种
3、i-4个排好了，有FFFF, FFFM, MFFF, FFMM, MFFM, MMFF, MMMM这么多种，其中最后是M的跟第一种冲突，最后是FF的跟第二种冲突，只剩FFFF了，所以有f[i-4]种
至于高精度处理看高精度模板，至于数据存储需要灵活处理
1 #include<stdio.h>
2 #include<string.h>
3 int f[1001][300]={{1,1},{1,1},{1,2},{1,4}};
4 void add(int *p,int *q,int *sum)
5 {
6 int len,i;
7 if(q[0]<p[0]) len=p[0];
8 else len=q[0];
9 for(i=1;i<=len;i++)
10 {
11 sum[i]+=q[i]+p[i];
12 if(sum[i]>9){sum[i]-=10;sum[i+1]++;}
13 }
14 if(sum[i]>0)len++;
15 sum[0]=len;
16 }
17 int main()
18 {
19 int i,n,ss[300];
20 for(i=4;i<1001;i++)
21 {
22 memset(ss,0,sizeof(ss));
23 add(f[i-1],f[i-2],ss);
24 add(ss,f[i-4],f[i]);
25 }
26 while(scanf("%d",&n)!=EOF)
27 {
28 for(i=f[n][0];i>0;i--)
29 printf("%d",f[n][i]);
30 printf("\n");
31 }
32 return 0;
33 }