题目链接
Children’s Queue HDU - 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?
Input
There are multiple cases in this problem and ended by the EOF. In each case, there is only one integer n means the number of children (1<=n<=1000)
Output
For each test case, there is only one integer means the number of queue satisfied the headmaster’s needs.
Sample Input
1
2
3
Sample Output
1
2
4
题意
n个学生排队，要求女生不能单独站一起，即要么队伍中没有女生，要么两个及两个以上的女生站一起。求n个学生的男女排队方式有多少种。
分析
求合法队列种数问题一般考虑递推。
设dp[n]表示n个学生的合法队列数。现要将第n个人入队。
如果第n个人是男生，要想队列合法，那么前n-1个人组成的队列必须合法，这种情况的数量有dp[n-1]种。
如果第n个人是女生，要想队列合法，第n-1个人必须是女生。
然后再分析前n-2个人：
前n-2个人组成的队列合法，显然符合条件，有dp[n-2]种。
前n-2个人组成的队列不合法，即第n-3个人是男，第n-2个人是女。因为第n-1和第n个人确定是女，所以这种可能是符合条件的，有dp[n-4]种。
故dp[n]=dp[n-1]+dp[n-2]+dp[n-4]。
AC代码
import java.math.BigInteger;
import java.util.Scanner;public class Main{static BigInteger[] dp=new BigInteger[1010];public static void main(String[] args) {Scanner cin=new Scanner(System.in);init();while(cin.hasNext()) {int n;n=cin.nextInt();System.out.println(dp[n]);}}public static void init() {dp[1]=new BigInteger("1");dp[2]=new BigInteger("2");dp[3]=new BigInteger("4");dp[4]=new BigInteger("7");for(int i=5;i<dp.length;i++) {dp[i]=dp[i-1].add(dp[i-2]).add(dp[i-4]);}}
}