hdu1297 参考答案

   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 }