题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1297

题目描述

There are many students in PHT School. One day, the headmaster whose name is PigHeader wanted all students stand in a line. He prescribed that girl can not be in single. In other words, either no girl in the queue or more than one girl stands side by side. The case n=4 (n is the number of children) is like

FFFF, FFFM, MFFF, FFMM, MFFM, MMFF, MMMM

Here F stands for a girl and M stands for a boy. The total number of queue satisfied the headmaster’s needs is 7. Can you make a program to find the total number of queue with n children?

思路

设:F(n)表示n个人的合法队列,则:

按照最后一个人的性别分析,他要么是男,要么是女,所以可以分两大类讨论:

  1. 如果n个人的合法队列的最后一个人是男,则对前面n-1个人的队列没有任何限制,他只要站在最后即可,所以,这种情况一共有F(n-1);
  2. 如果n个人的合法队列的最后一个人是女,则要求队列的第n-1个人务必也是女生,这就是说,限定了最后两个人必须都是女生,这又可以分两种情况:
    2.1 如果队列的前n-2个人是合法的队列,则显然后面再加两个女生,也一定是合法的,这种情况有F(n-2);
    2.2 但是,难点在于,即使前面n-2个人不是合法的队列,加上两个女生也有可能是合法的,当然,这种长度为n-2的不合法队列,不合法的地方必须是尾巴,就是说,这里说的长度是n-2的不合法串的形式必须是“F(n-4)+男+女”,这种情况一共有F(n-4).

所以,通过以上的分析,可以得到递推的通项公式:
$$F(n)=F(n-1)+F(n-2)+F(n-4) (n>3)$$

然后就是对n<=3的一些特殊情况的处理了,显然:

  1. F(0)=1 (没有人也是合法的,这个可以特殊处理,就像0的阶乘定义为1一样)
  2. F(1)=1 F(2)=2 F(3)=4

AC代码

/*************************************************************************
    > File Name: 1297.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: Tue 26 May 2015 09:55:59 AM CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

int f[1005][100];
void add(int n) {
    int k = 0;
    int j;
    for(j=1; j<=100; ++j) {
        k+=f[n-1][j] + f[n-2][j] + f[n-4][j];
        if(k==0)
            break;
        f[n][j] = k%10000; // 大数处理
        k/=10000;
    }
}
int main()
{
#ifdef Oj
#endif
    f[1][1] = 1;
    f[2][1] = 2;
    f[3][1] = 4;
    f[4][1] = 7;

    for(int n=5; n<=1000; ++n)
        add(n);
    int n, i;
    while(cin >> n) {
        for(i=100; i>0; --i)
            if(f[n][i]!=0) break;
        printf("%d", f[n][i]);
        for(--i; i>0; --i)
            printf("%04d", f[n][i]);
        printf("\n");

    }
    return 0;
}