第一次写博客。

Problem 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矩形，用2*1的矩形将它填满，有多少种情况。

这是一题递推题，首先当n为奇数的时候，3*奇数=奇数，用2*1的矩形是怎样都填不下去的。

所以只要考虑n为偶数的情况。

设3*n时情况有a[n]种；

当n=2时，有以下三种情况：

 

当n>2时，

如果图形中不包含n=2时的三种情况的话，那么就只会有2种情况。

例如n=4：

将其反过来又是一种。

根据以上两种情况可以将长为n的矩形分两块：n-2+2；n-4+4；n-6+6……n-n+n；

①n-2+2的情况有a[n-2]*3;

②n-4+4的情况有a[n-4]*2;为什么这里是*2而不是*a[4]?因为4分成2与2的话会与②中的重复，所以只需考虑4中不能分成2与2情况

……

所以a[n]=a[n-2]*3+2*（a[n-4]+a[n-6]+……+a[n-(n-2)]+a[0](注意a[0]=1)）;

#include
      
       int a[35]={
    1,0,3};int f(int x){    int sum=0;    for(int i=x;i>=0;i-=2)    sum+=a[i]*2;    return sum;}int main(){    int n;    for(int i=4;i<=30;i+=2)    {        a[i]=a[i-2]*3+f(i-4);        a[i-1]=0;    }    while(scanf("%d",&n)!=EOF)    {        if(n==-1)        break;        printf("%d\n",a[n]);    }}