POJ 3797 - Tiling a Grid With Dominoes

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

概要

2 x 1 の長方形を使って何通りの方法で 4 x W の長方形を作ることができるかを答える．

制約

• 答えは 32-bit の整数に収まる

解法

漸化式を立てて計算するだけ． W はだいたい 30 くらいまでなのでメモ化は必要無いかなと思いつつ，一応メモ化再帰で計算した．

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int dp[30];
 5 int f(int w)
 6 {
 7   int &a = dp[w];
 8   if (a != 0) {
 9     return a;
10   } else {
11     a += f(w-1);
12     a += 4*f(w-2);
13     for (int i = 3; i <= w; i++) {
14       a += (i & 1 ? 2 : 3) * f(w-i);
15     }
16     return a;
17   }
18 }
19 
20 int main()
21 {
22   dp[0] = dp[1] = 1;
23   int T;
24   cin >> T;
25   for (int Ti = 1; Ti <= T; Ti++) {
26     int w;
27     cin >> w;
28     cout << Ti << ' ' << f(w) << endl;
29   }
30   return 0;
31 }