UVa 10918 - Tri Tiling

Contents

1. 1. Problem
2. 2. Solution
3. 3. Code

Problem

題目網址
中文網址

Solution

如果 n 為奇數則不可能組成。

我們可以從中找到規律:

先定義 dp[i] 為 n = i 時:

• i 為偶數 : 可組成完整矩形的組合數
• i 為奇數 : 可組成矩形少一角的組合數

n = 0 時 只有一種。

在 n = 1 時，有兩種可能，分別為 x 的位置是空的:

1 x o o

1 o o x

n = 2 時，

* 我們將空的角補滿再填上新的一塊，從 n = 1 的延伸:

1 a a b
2 c c b

1 b a a
2 b c c

* 從 n = 0 延伸(不包含 n = 1 的情況):

1 a b c
2 a b c

接著 n = 3 的情況

* 從 n = 2 延伸:

1 a a b
2 c c b
3 d d x

1 a a b
2 c c b
3 x d d

...

其組合數為 dp[2] * 2 。

* 從 n = 1 延伸:

1 a a b
2 c d b
3 c d x

1 b a a
2 b d c
3 x d c

其組合數為 dp[1] 。

n = 4 時:

• 我們將空的角補滿再填上新的一塊，從 n = 3 的延伸:
  其組合數為 dp[3]

• 從 n = 2 延伸:
  其組合數為 dp[2]

總結以上可以歸納出:

• i 為偶數: dp[i] = dp[i-1] + dp[i-2]
• i 為奇數: dp[i] = 2 * dp[i-1] + dp[i-2]

Code

UVa 10918

#include<cstdio>

int main()
{
    int n, ans[32] = { 1, 2 };
    for (int i = 2; i < 31; i++)
    {
        ans[i] = ans[i - 1] + ans[i - 2];
        ans[++i] = 2 * ans[i - 1] + ans[i - 2];
    }

    while (scanf("%d", &n) && n != -1)
        printf("%d\n", n & 1 ? 0 : ans[n]);

    return 0;
}