⇤ ← 于2008-09-24 14:26:05修订的的版本1
1483
备注:
|
1496
|
删除的内容标记成这样。 | 加入的内容标记成这样。 |
行号 2: | 行号 2: |
#!cplusplus |
1 /*
2 hdu1297
3 ymc 2008/9/24
4
5 题目大意:
6
7 分析与解题思路
8 设:F(n)表示n个人的合法队列,则:
9 按照最后一个人的性别分析,他要么是男,要么是女,所以可以分两大类讨论:
10 1、如果n个人的合法队列的最后一个人是男,则对前面n-1个人的队列没有任何限制,他只要站在最后即可,所以,这种情况一共有F(n-1);
11 2、如果n个人的合法队列的最后一个人是女,则要求队列的第n-1个人务必也是女生,这就是说,限定了最后两个人必须都是女生,这又可以分两种情况:
12 注意:大整数
13 */
14 #include <iostream>
15 using namespace std;
16 const int N=1100;
17 const int M=500;
18 struct Big
19 {
20 int s[M];
21 int len;
22 };
23 Big f[N];
24 void Add(Big &a,Big &b,Big &c,Big &d)
25 {
26 d.len=a.len;
27 int t=0;
28 for(int i=0;i<d.len;i++)
29 {
30 t+=a.s[i]+b.s[i]+c.s[i];
31 d.s[i]=t%10;
32 t=t/10;
33 }
34 if(t>0)
35 {
36 d.s[d.len]=t;
37 d.len++;
38 }
39 }
40 void OutPut(Big &a)
41 {
42 for(int i=a.len-1;i>=0;i--)
43 printf("%d",a.s[i]);
44 printf("\n");
45 }
46 void Init()
47 {
48 f[0].s[0]=1;f[0].len=1;
49 f[1].s[0]=1;f[1].len=1;
50 f[2].s[0]=2;f[2].len=1;
51 f[3].s[0]=4;f[3].len=1;
52 for(int i=4;i<N;i++)
53 {
54 Add(f[i-1],f[i-2],f[i-4],f[i]);
55 }
56
57 }
58
59 int main()
60 {
61 int n;
62 Init();
63 while(scanf("%d",&n))
64 {
65 OutPut(f[n]);
66 }
67 }