hdu 1297 Children’s Queue 递推

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1297

题意：求n个人排成一列的方案数，其中男女数量无规定，但是女生至少要两个站在一起。

思路：由于有男生和女生，所以n个人排成一列共有2^n种方案。可将这2^n种方案分为合法序列和非合法序列，并设合法序列方案数为F(n)。

要注意，每增加一个人，总方案数会变成原来的两倍。

我们可以想像n-1个人的所有可能的序列已经排好，增加一个人就是在原来排好的序列的末尾加上一个男生或一个女生。

有人会问：为什么只在末尾加，在前面加人不可以吗？

其实在前在后加都是一样的，n-1个人排成的序列有2^n-1种，n个人排成的序列有2^n种，这是不变的。

理解这点后，就可以通过前面的状态求解F(n)

1、末尾加男生

可以知道，在合法序列后面加一个男生，它依旧是合法序列；在不合法序列加一个男生，它依旧是不合法序列。所以加男生的方案是F(n-1)种

进一步：可否在n-2的情况下加2个男生，或在n-x的情况下加x个男生？不可以，因为会重复。

2、末尾加女生的话，考虑通过n-2的序列再加两个女生。

这又有两种情况：

（1）在合法序列后面加两个女生，即F(n-2)

（2）在不合法序列后面加女生，这种情况只有在末尾只有一个女生这种不合法序列才奏效，因为只有这种才能通过在后面加一个女生变成合法序列。

F(n-4) + 男 + 女

所以递推式：F(n) = F(n-1) + F(n-2) + F(n-4).

由于数据比较大，要用到大数。

  1 #include<iostream>
  2 #include<string>
  3 #include<iomanip>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<algorithm>
  7 using namespace std;
  8
  9 #define MAXN 9999
10 #define MAXSIZE 10
11 #define DLEN 4
12
13 class BigNum
14 {
15 private:
16     int a[500];    //可以控制大数的位数
17     int len;       //大数长度
18 public:
19     BigNum(){ len = 1;memset(a,0,sizeof(a)); }   //构造函数
20     BigNum(const int);       //将一个int类型的变量转化为大数
21     BigNum(const BigNum &);  //拷贝构造函数
22     BigNum &operator=(const BigNum &);   //重载赋值运算符，大数之间进行赋值运算
23
24     BigNum operator+(const BigNum &) const;   //重载加法运算符，两个大数之间的相加运算
25
26     void print();       //输出大数
27 };
28 BigNum::BigNum(const int b)     //将一个int类型的变量转化为大数
29 {
30     int c,d = b;
31     len = 0;
32     memset(a,0,sizeof(a));
33     while(d > MAXN)
34     {
35         c = d - (d / (MAXN + 1)) * (MAXN + 1);
36         d = d / (MAXN + 1);
37         a[len++] = c;
38     }
39     a[len++] = d;
40 }
41
42 BigNum::BigNum(const BigNum & T) : len(T.len)  //拷贝构造函数
43 {
44     int i;
45     memset(a,0,sizeof(a));
46     for(i = 0 ; i < len ; i++)
47         a[i] = T.a[i];
48 }
49 BigNum & BigNum::operator=(const BigNum & n)   //重载赋值运算符，大数之间进行赋值运算
50 {
51     int i;
52     len = n.len;
53     memset(a,0,sizeof(a));
54     for(i = 0 ; i < len ; i++)
55         a[i] = n.a[i];
56     return *this;
57 }
58
59 BigNum BigNum::operator+(const BigNum & T) const   //两个大数之间的相加运算
60 {
61     BigNum t(*this);
62     int i,big;      //位数
63     big = T.len > len ? T.len : len;
64     for(i = 0 ; i < big ; i++)
65     {
66         t.a[i] +=T.a[i];
67         if(t.a[i] > MAXN)
68         {
69             t.a[i + 1]++;
70             t.a[i] -=MAXN+1;
71         }
72     }
73     if(t.a[big] != 0)
74         t.len = big + 1;
75     else
76         t.len = big;
77     return t;
78 }
79
80 void BigNum::print()    //输出大数
81 {
82     int i;
83     cout << a[len - 1];
84     for(i = len - 2 ; i >= 0 ; i--)
85     {
86         cout.width(DLEN);
87         cout.fill('0');
88         cout << a[i];
89     }
90     cout << endl;
91 }
92 int main(void)
93 {
94     int i,n;
95     BigNum x[1010];      //定义大数的对象数组
96     x[1]=1;
97     x[2]=2;
98     x[3]=4;
99     x[4]=7;
100     for(i=5;i<=1000;i++)
101         x[i]=x[i-1]+x[i-2]+x[i-4];
102     while(scanf("%d",&n)!=EOF)
103     {
104         x[n].print();
105     }
106     return 0;
107 }

View Code

hdu 1297 Children’s Queue 递推

相关推荐