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;
}