スレッド: HTTP://vn.spoj.pl/problems/M3TILE/

3XN 2長方形のドミノで舗装方法を数えます×1?

入力は、いくつかのテストケースの端が数値である含まれてい -1.
各テストケースは、整数nであります, 0 ≤N≤ 30.
各テストケースのための, 整数は、1行の回答に印刷されています.
サンプル入力
2
8
12
-1
サンプル出力
3
153
2131
時間: 1S
注目: N = 0が返さ結果は 1.

この記事では、nにセル1奇数であります×1 子どもたちはdomioている間奇数であります 2 傘, その合計は常に偶数, 結果は、問題のリターンであります 0 適切な方法の評価があります. だから我々は、n個のパリティを検討します.
最初のレビューを矩形3×2, 簡単に気づきました 3 載

3考えると複数の矩形×4, 3 X 3 = 9 から + 2 => 11 から

3考えると複数の矩形×6, 我々は、次の場合を持っています:

fが呼び出された場合(へ) 方法の長方形のスライスが、我々は3xkを持っています:
F(6) = F(2) * F(6-2) + 2*[ F(6-4) + F(6-6) ] = 3*11 + 2*(3+1) = 41 から.
一般的には持っています:
F(へ) = 3 * F(K-2) + 2*[ F(K-4) + F(K-6) + .. + F(0) ]
=> F(へ) + F(K-4) = 3 * F(K-2) + 3*F(K-4) + 2*[ F(K-6) + F(K-8) + .. + F(0) ]
=> F(へ) + F(K-4) = 3 * F(K-2) + F(K-2) = 4 * F(K-2)
=> F(へ) = 4 * F(K-2) – F(K-4)
その式は、次の簡単な検索を発見されました:
F(へ) = 4 * F(K-2) – F(K-4) fは(0) = 1, F(2) = 3
F(N) 問題の解であります. 次のようにインストールします (時間: 0.01s 🙂 )

#include<stdio.h>
int main()
{
    int n,i;
    int f[31]={0};
    f[0]=1;
    f[1]=0;
    f[2]=3;
    f[4]=11;
    for(i=6;i<=30;i+=2)
       f[i]=4*f[i-2] - f[i-4];
    scanf("%d",&n);
    while(n!=-1)
    {
       printf("%dn",f[n]);
       scanf("%d",&n);
    }
    return 0;
}