hdu 1297 Children’s Queue（大数处理）

发布时间：2020-12-14 03:32:50 所属栏目：大数据来源：网络整理

导读：链接：hdu 1297 Problem Description There are many students in PHT School. One day,the headmaster whose name is PigHeader wanted all students stand in a line. He prescribed that girl can not be in single. In other words,either no girl in th

链接：hdu 1297

Problem Description

There are many students in PHT School. One day,the headmaster whose name is PigHeader wanted all students stand in a line. He prescribed that girl can not be in single. In other words,either no girl in the queue or more than one girl stands side by side. The case n=4 (n is the number of children) is like
FFFF,FFFM,MFFF,FFMM,MFFM,MMFF,MMMM
Here F stands for a girl and M stands for a boy. The total number of queue satisfied the headmaster’s needs is 7. Can you make a program to find the total number of queue with n children?

Input

There are multiple cases in this problem and ended by the EOF. In each case,there is only one integer n means the number of children (1<=n<=1000)

Output

For each test case,there is only one integer means the number of queue satisfied the headmaster’s needs.

Sample Input

Sample Output

题意：n个人站成一队，女生不能单独站着，即如果有女生必须至少有两个女生相邻（可以没有女生），

? ? ? 问有多少种排法

分析：情况一：（最后是以男生结尾的）这时候是：f[n-1]+男； ???????????

? ? ? 情况二：（最后是以女生结尾的） ??????????

?????????????? 1.这时候有可能：f[n-2]+女+女 ?????????????????

? ? ? ? ? ? ? ?2.还有可能：f[n-4]+男+女+女+女

? ? ?所以最后的递推式是：f[n]=f[n-1]+f[n-2]+f[n-4];

注：数较大，要用大数处理

AC代码：

#include<stdio.h>
int a[1001][101]={0};
int main()
{
    int i,j,n,m;
    a[1][0]=1;
    a[2][0]=2;
    a[3][0]=4;
    a[4][0]=7;
    for(i=5;i<=1000;i++)
        for(j=0;j<=100;j++){
            a[i][j]+=a[i-1][j]+a[i-2][j]+a[i-4][j];
            m=a[i][j]/10000;
            a[i][j]%=10000;
            a[i][j+1]+=m;
        }
    while(scanf("%d",&n)!=EOF){
        for(i=100;i>=0;i--)
            if(a[n][i]!=0)
                break;
        printf("%d",a[n][i]);
        for(j=i-1;j>=0;j--)
            printf("%04d",a[n][j]);
        printf("n");
    }
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!