hdoj 1297 Children’s Queue 【高精度】【递推】

题意：有n个人，每一个人可以是男孩也可以是女孩，要求每个女孩不能单独一个，也就是一个女孩的左右紧挨的位置至少要有一个女孩。问这样的队列有几个。

分析：设f（n）是n的排列的数目，这时候来一个人：

一：如果是男孩，那么f（n ） = f（n-1）

二：如果是女孩，如果前n-2是合法的，那么f（n） = f（n-2）；如果前n-2不合法的，那么n-2队列的末尾两个同学肯定是男+女，那么再加上后来的女孩，又合法了，此时f(n) = f(n-4);

综上：f(n) = f(n-1)+f(n-2)+f(n-4);

又因为数据范围比较大，要用高精度。

代码：

#include <stdio.h>
#include <string.h>
#define M 1050
int a[M][M];
void table(){
    int i,j;
    memset(a,sizeof(a));
    a[1][0] =1; a[2][0] = 2; a[3][0] = 4; a[4][0] = 7;
    for(i = 5; i < 1050; i ++){
        for(j = 0; j < M; j ++) 
            a[i][j] = a[i-1][j]+a[i-2][j]+a[i-4][j];
        for(j = 0; j < M; j ++){
            if(a[i][j] >= 10){
                int temp = a[i][j]/10;
                a[i][j]%=10;
                a[i][j+1] += temp;
            }
        }
    }
}
int main(){
    table();
    int n,i,j;
    while(scanf("%d",&n) == 1){
        i = M-1;
        while(a[n][i] == 0) i --;
        printf("%d",a[n][i]);
        while((--i) >= 0) printf("%d",a[n][i]);
        puts("");
    }
    return 0;
}