Tri Tiling - POJ 2663 遞推

Tri Tiling

Time Limit: 1000MS	Memory Limit: 65536K
Total Submissions: 7918	Accepted: 4151

Description

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*N的矩形用1*2的小方塊鋪滿，一共有多少種方式。

思路：首先奇數的話不行，偶數的話，遞推公式是f(n)=4*f(n-2)-f(n-4)。

AC代碼如下：

#include<cstdio>
#include<cstring>
using namespace std;
int num[35];
int main()
{
    int n,i,j,k;
    num[0]=1;num[2]=3;
    for(i=4;i<=30;i++)
       num[i]=4*num[i-2]-num[i-4];
    while(scanf("%d",&n) && n>=0)
       printf("%d\n",num[n]);
}