|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 |
<strong>Children’s Queue</strong>Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 9545 Accepted Submission(s): 3049Problem DescriptionThere 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
likeFFFF, FFFM, MFFF, FFMM, MFFM, MMFF, MMMMHere 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? InputThere 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) OutputFor each test case, there is
only one integer means the number of queue satisfied the headmaster’s needs. Sample Input123 Sample Output124 |
递推式去杭电ppt看，fn=fn-1+fn-2+fn-4.这个求出来fn的值会非常大，需要用数组存。
#include<stdio.h> #include<iostream> #include<string> #define MAXM 1001 #define MAXN 502 using namespace std; int a[MAXM][MAXN]; int main() { int n, t, p, i, j; memset(a, 0, sizeof(a)); a[1][0] = 1; a[2][0] = 2; a[3][0] = 4; a[4][0] = 7; for (i = 5; i<MAXM; i++){ for (j = 0; j<MAXN; j++){ a[i][j] += a[i - 1][j] + a[i - 2][j] + a[i - 4][j]; if (a[i][j] >= 10){ a[i][j + 1] += a[i][j] / 10; a[i][j] %= 10; } } } while (scanf("%d", &n) != -1){ for (i = 500; a[n][i] == 0; i--); for (; i>-1;i--) { printf("%d", a[n][i]); } printf("\n"); } return 0; }
原文：http://www.cnblogs.com/littlehoom/p/3551423.html