Tiling

c[0]=1,c[1]=1,c[2]=3;   c[n]=c[n-1]+c[n-2]*2;   0<=n<=250.   大数加法

java  time  :313ms

1 import java.util.*;
2 import java.math.*;
3 public class Main
4 {
5 static int MS=251;
6 static BigInteger[] ans;
7
8 public static void main(String[] args)
9 {
10 Scanner cin=new Scanner(System.in);
11 ans=new BigInteger[MS];
12 ans[0]=BigInteger.valueOf(1); // 注意这里n==0的时候，ans=1;
13 ans[1]=BigInteger.valueOf(1);
14 ans[2]=BigInteger.valueOf(3);
15 for(int i=3;i<MS;i++)
16 ans[i]=ans[i-1].add(ans[i-2].multiply(BigInteger.valueOf(2)));
17 int n;
18 while(cin.hasNextInt())
19 {
20 n=cin.nextInt();
21 System.out.println(ans[n]);
22 }
23 cin.close();
24 }
25 }