CUC-SUMMER-5-B

B - Tri Tiling

HDU - 1143

---

In how many ways can you tile a 3xn rectangle with 2x1 dominoes? Here is a sample tiling of a 3x12 rectangle.

Input
Input consists of several test cases followed by a line containing -1. Each test case is a line containing an integer 0 ≤ n ≤ 30.

Output
For each test case, output one integer number giving the number of possible tilings.

Sample Input
2
8
12
-1

Sample Output
3
153
2131

---

题意：瓷砖问题，3 x n的区域用3 x 1的瓷砖铺一共有多少种方案。

解法：dp算法，递推，有三种基础排法，所以f(n)=3f(n-2)，但还要考虑与前面相连的情况，所以f(n)=3f(n-2)+2f(n-4)+2f(n-6)+······+2f(2)，所以得到f(n)=4*f(n-2)-f(n-4)

代码：

#include<iostream>
using namespace std;
int main()
{
    int a[31]={0,};
    a[0]=1,a[2]=3;
    for(int i=4;i<=30;i+=2)
        a[i]=4*a[i-2]-a[i-4];
    int n;
    while(cin>>n&&n!=-1)
        cout<<a[n]<<endl;
    return 0;
}