HDU 1297 Children’s Queue

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

題面：

Children’s Queue Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 13363????Accepted Submission(s): 4379


Problem Description 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 ?
Author SmallBeer (CML) ?
題目大意： ? ? 給定隊(duì)伍長(zhǎng)度，求不出現(xiàn)單獨(dú)一個(gè)女生的方案數(shù)。
解題： ? ? 可以用dp三維來(lái)解決這個(gè)問(wèn)題。dp[i][j][k],i表示是第i位，j為1表示男生，j為0表示女生，k為0表示0個(gè)女生，k為1表示1個(gè)女生，k為2表示多個(gè)女生，即合法狀態(tài)。 ? ? 遞推關(guān)系如下： ? ? ?

dp[i+1][0][2]=dp[i+1][0][2].add(dp[i][0][1]);
dp[i+1][0][2]=dp[i+1][0][2].add(dp[i][0][2]);
dp[i+1][1][0]=dp[i+1][1][0].add(dp[i][0][2]);
dp[i+1][1][0]=dp[i+1][1][0].add(dp[i][1][0]);
dp[i+1][0][1]=dp[i+1][0][1].add(dp[i][1][0]);

部分狀態(tài)雖然不符合最后的要求，即女生不可落單，但計(jì)算過(guò)程中需要用到相應(yīng)值，最后的答案為，dp[n][1][0]+dp[n][0][2]

代碼：

import java.io.*;
import java.util.*;
import java.math.*;
public class Main{
	public static void main(String args[])
	{
		BigInteger dp[][][]=new BigInteger [1005][2][3];
		Scanner sc =new Scanner(new BufferedInputStream(System.in));
		PrintWriter cout=new PrintWriter(System.out);
		for(int i=0;i<=1004;i++)
			for(int j=0;j<=1;j++)
				for(int k=0;k<=2;k++)
					dp[i][j][k]=BigInteger.ZERO;
		dp[1][0][1]=BigInteger.valueOf(1);
		dp[1][1][0]=BigInteger.valueOf(1);
		for(int i=1;i<=1000;i++)
		{
			dp[i+1][0][2]=dp[i+1][0][2].add(dp[i][0][1]);
			dp[i+1][0][2]=dp[i+1][0][2].add(dp[i][0][2]);
			dp[i+1][1][0]=dp[i+1][1][0].add(dp[i][0][2]);
			dp[i+1][1][0]=dp[i+1][1][0].add(dp[i][1][0]);
			dp[i+1][0][1]=dp[i+1][0][1].add(dp[i][1][0]);
		}
		int t;
		while(sc.hasNext())
		{
           t=sc.nextInt();
		   cout.println(dp[t][0][2].add(dp[t][1][0]));
		}
		cout.flush();
	}
}