HDU 1297 Children’s Queue （递推、大数相加）

时间：2022-02-01 09:14:12

Children’s Queue

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 17918    Accepted Submission(s): 5976

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个小朋友有多少种坐法


题目分析


首先长度为1时，只有1种可能，即“M”；


　　长度为2时，有2种可能，即“FF”和“MM”;


　　长度为3时，有4种可能，即“FFF”、“FFM”、“MFF”和“MMM”;


　　长度为4时，有7种可能，即“FFFF”、“FFFM”、“FFMM”、“MFFM”、“MFFF”、“MMFF”、“MMMM”;
当n>4时，我们可以这么想：
　　如果第n个人是M，符合条件，这样的情况有f(n-1)个，因为是直接在n-1的情况下在最后加上了一个M


　　如果第n个人是F，那么就需要考虑倒数第二个人，如果倒数第二个人是F，这是可以的，那么也就相当于 在n-2的基础上加了一个FF


　　　　　　　　　　但是注意，刚刚我们是在n-2的基础上加了一个FF，也就是说，默认前n-2是合理的，但是也存在不合理的情况 也就是说 前面n-2是以MF结尾的，这时候加上FF也是合理的，也就相当于在n-4的基础上加上了MFFF


综上 我们可以列出来递推方程：
　　f(n) = f(n-1)+f(n-2)+f(n-4)


剩下的就只是将大数模板套进去就好了


代码：




#include<bits/stdc++.h>

using namespace std;

int n,i;

string bigadd(string a,string b)

{

    int jin=,i;

    char ai,bi;

    string anss=a;

    int lena=a.size();

    int lenb=b.size();

    int lenmax=max(lena,lenb);

    int p=lena-;

    int q=lenb-;

    for(i=lenmax-;i>=;i--)

    {

        if(p<)

        ai='';

        else

        ai=a[p];

        if(q<)

        bi='';

        else

        bi=b[q];

        anss[i]=((ai-''+bi-''+jin)%)+'';

        jin=(ai-''+bi-''+jin)/;

        p--;

        q--;

    }

    if(jin)

    {

        char x=jin+'';

        anss=x+anss;

    }

    return anss;

}

 int main()

 {

    string a[];

    a[]="";

    a[]="";

    a[]="";

    a[]="";

    for(i=;i<;++i)

           a[i]=bigadd(bigadd(a[i-],a[i-]),a[i-]);  //这里需要注意的是，我之前用的是bigadd(bigadd(a[i-4],a[i-2]),a[i-1])，但是WA了，我仔细想了想，这是由于我的大数相加模板导致的，如果后加的数比前面的数位数大，就会出现位数丢失的问题，所以必须先将最大的a[i-1]与a[i-2]相加。

    while(scanf("%d",&n)!=EOF)

    {

        cout<<a[n]<<endl;

    }

    return ;

}


相关文章