POJ 2506 - Tiling

http://poj.org/problem?id=2506

概要

2x1 のタイルと 2x2 のタイルがある． これらで何通りの 2xn の長方形を作れるか答える．

制約

• 0 <= n <= 250

解法

dp[n] = dp[n-1] + 2 * dp[n-2]

という DP．

サンプルを見ての通り long long にも余裕で収まらないので BigInteger．

 1 import java.util.*;
 2 import java.math.*;
 3 
 4 public class Main {
 5   public static void main(String[] args) {
 6     BigInteger[] dp = new BigInteger[251];
 7     dp[0] = dp[1] = BigInteger.ONE;
 8     for (int i = 2; i <= 250; i++) {
 9       dp[i] = dp[i-1].add(dp[i-2].multiply(BigInteger.valueOf(2)));
10     }
11 
12     Scanner cin = new Scanner(System.in);
13     while (cin.hasNextInt()) {
14       int n = cin.nextInt();
15       System.out.println(dp[n]);
16     }
17   }
18 }