递推 + 大数 HDU1297

 1 import java.math.*;
 2 import java.util.*;
 3 
 4 public class Main
 5 {
 6     static BigInteger arr[] = new BigInteger [1000000];
 7     public static void main(String[] args)
 8     {
 9         Scanner cin=new Scanner(System.in);
10         int n;
11         while(cin.hasNext())
12         {
13             n=cin.nextInt();
14             arr[0]=BigInteger.valueOf(1);
15             arr[1]=BigInteger.valueOf(1);
16             arr[2]=BigInteger.valueOf(2);
17             arr[3]=BigInteger.valueOf(4);
18             arr[4]=BigInteger.valueOf(7);
19             for(int i=5;i<=n;i++)
20             {
21                 arr[i]=BigInteger.ZERO;
22                 arr[i]=arr[i].add(arr[i-1]);
23                 arr[i]=arr[i].add(arr[i-2]);
24                 arr[i]=arr[i].add(arr[i-4]);
25             }
26             System.out.println(arr[n]);
27         }
28     }
29 }

View Code

F[n]代表到n位置结尾，是序列合法的排列种数

如果最后一个位置是男，只需前n-1个位置合法即可

如果最后一个位置是女，有两种可能：

　　1. 前n-1个位置不合法，即第n-1个位置为单个女，而此时需要前n-2个位置合法

　　2. 前n-1个位置合法，即第n-1，n-2位置都为女，n-3位置为男，而此时需要前n-4个位置合法，为什么不是n-3呢？因为如果要求前n-3个位置合法，就会出现和上种可能重复的情况，例如：女，女，女，女，这就满足这两种可能

所以F[N]=F[N-1]+F[N-2]+F[N-4];