POJ 2663 - Tri Tiling

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

概要

3 * n の長方形を 2 * 1 のドミノで敷き詰める方法が何通りあるか答える．

制約

• 0 <= n <= 30

解法

3 * n の敷き詰め方が a[n] 通りだとする．

n が奇数のときは明らかに 0 通り．

n が偶数のときは，a[n-2] に対して

の3通りの追加の仕方があり，また ai に対して

のような形で2通りの追加の仕方がある (図は i = n-4 のとき)．

よって，

• a[0] = 1
• a[n] = 0 if n is odd
• a[n] = 3*a[n-2] + sum[i = 0, 2, ..., n-4]{ 2*a[i] } if n is even

という漸化式を満たすので，これに従って最初に表を作っておいて答える．

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6   int a[31];
 7   a[0] = 1;
 8   a[1] = 0;
 9   for (int i = 2; i <= 30; i++) {
10     if (i % 2 == 0) {
11       a[i] = 3*a[i-2];
12       for (int j = 0; j <= i-4; j += 2) {
13         a[i] += 2*a[j];
14       }
15     } else {
16       a[i] = 0;
17     }
18   }
19 
20   int n;
21   while (cin >> n && n != -1) {
22     cout << a[n] << endl;
23   }
24   return 0;
25 }