hdu 1143 Tri Tiling 递推

http://acm.hdu.edu.cn/showproblem.php?pid=1143

主要是题目的理解啊，推出递推公式就好做了。

我们可以看到，当   x   = 2 时，有三种情况，三 横，一横  两竖，两竖 一横、

那么当x > 2   时，把他分割成不可分割的部分是什么情况呢. 如果是4个的情况下，上面放上一横，下面如果还是放横的话，就和x  = 2 的时候一样了，所以下面要放一竖 和两横，那么右边的自然也就固定了，这时候我们会发现，x  = 4 只有一种情况，如果我们把横放到下面就是对称的一种情况，所以总共有两种情况。

此时， 可以得出结论，当x  >   2 的时候，把它分割成不能被竖线分割的矩形就只有2种 情况。

所以可以得出递推公式  f (n) = 3 * f(n -2) + 2 * f(n -4) + .....+ 2 * f(0);

写出f(n-2)   ,  可得到  f（n） = 4 * f（n - 2） - f（n - 4）；

代码就很简单了

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