yt13递推Children’s Queue (大数)
发布时间:2020-12-14 03:39:44 所属栏目:大数据 来源:网络整理
导读:Children’s Queue Time Limit : 2000/1000ms (Java/Other)???Memory Limit : 65536/32768K (Java/Other) Total Submission(s) : 80???Accepted Submission(s) : 19 Font: Times New Roman | Verdana | Georgia Font Size: ← → Problem Description There
Children’s QueueTime Limit : 2000/1000ms (Java/Other)???Memory Limit : 65536/32768K (Java/Other)Total Submission(s) : 80???Accepted Submission(s) : 19Font: Times New Roman | Verdana | GeorgiaFont Size: ← →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 Input1 2 3 Sample Output1 2 4 AuthorSource
杭电ACM集训队训练赛(VIII)?
题目大意:主要要求是,n个人站一排,不允许女生单独站着,至少要有两个或两个以上女生咋还能在一块才合法。
思路:
1:最后一个人是男的,则只要前n-1个人的排列合法即可。
2:左后一个人是女的,则倒数第二个人必须是女的,则又分两种情况:
(1)前n-2个人的排列是合法的,则整个队列就是合法的。
(2)前n-2个不是合法的,则有这样的形式a[n-4]+男+女的形式才能使整个队列合法。
对于大数的处理,我采用的是数组,每个数组中的元素,只存10000以内的数,超过10000的在来个数组储存。
代码:
#include <iostream> #include<cstdio> using namespace std; int main() { int n,i,m,e,j; int a[1000],b[1000],c[1000],d[1000],f[1000];//定义数组,数组b,c,d,f分别存a[n-1],a[n-2],a[n-3],a[n-4]; while(cin>>n) { a[0]=1; a[1]=1; a[2]=2; a[3]=4; if(n>=4) { b[0]=4; c[0]=2; d[0]=1; f[0]=1; m=0; for(i=4; i<=n; i++) { e=0; for(j=0; j<=m; j++) { a[j]=b[j]+c[j]+d[j]+e;//相当于递推公式a[n]=a[n-1]+a[n-2]+a[n-4]; e=a[j]/10000;//判断是否超出了10000; a[j]=a[j]%10000;//保证数组只存10000以内的数 d[j]=f[j]; f[j]=c[j]; c[j]=b[j]; b[j]=a[j]; } if(e>0)//若超出则用新的数组来存; { m++; a[m]=e; b[m]=a[m]; c[m]=0; d[m]=0; f[m]=0; } } //cout<<a[0]<<endl; printf("%d",a[m]); // cout<<m<<endl; for(i=m-1; i>=0; i--) printf("%04d",a[i]); printf("n"); } else cout<<a[n]<<endl; } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |