Differences between revisions 1 and 2
Revision 1 as of 2008-09-24 14:26:05
Size: 1483
Editor: 218
Comment:
Revision 2 as of 2008-09-24 14:26:43
Size: 1496
Editor: 218
Comment:
Deletions are marked like this. Additions are marked like this.
Line 2: Line 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 }

hdu1297 参考答案 (last edited 2008-09-26 09:47:35 by czk)

ch3n2k.com | Copyright (c) 2004-2020 czk.