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