Morris' Blog

2013-07-18 10:16:22Morris

[UVA][math] 1224 - Tile Code

留言 0 收藏 0 推薦 0

韓國松波區現在著手進行一個腳踏車系統規劃，名為 "綠色松波"。在今年年底，市民和遊客都可以在整座城市中使用自行車，近期決定在自行車上數字標記，以方便管理。自行車將會在城市交通系統的管理控制下。

數字標記為一條長度為 n 的磚瓦條碼，每個將由 1 x 2, 2 x 1, 2 x 2 的磚瓦所構成，而條碼將會是個 2 x n 的長方形板子，每個方格只會由一個磚瓦覆蓋，長方形板子可以畫分成 2n 個 1 x 1 的方格。當然兩個磚瓦不會有重疊的部分，如下圖一是個 2 x 5 的 n = 5 長方形板，而圖二則是其中一種擺放方式，雖然條碼總是由左而右去讀，但是卻沒有上下之分，因此圖二和圖三是屬於同一種條碼。

給一個正整數 n，專案負責人 Dr. Yang 想要知道當長度為 n 時，有多少磚瓦條碼可以被使用，限定放入上述三種磚瓦於 2 x n 的長方形板。

Input

第一行會有會有一個整數 T ，表示接下來有多少組測資。
每組測資會有一個正整數 n，3 <= n <= 30。

Output

對於每組測資，輸出方法數。

Sample Input

2 
3 
4

Sample Output

3 
8

這裡就不放原文了，因為原題圖片有點問題。

題目是要找不考慮左邊看過去跟右邊看過去的不同種排法有多少。

首先不考慮對稱的情況計算，以及只有對稱的個數。

因此答案會是 (全部排法+只有對稱的個樹)/2

由於奇偶數比較特別，考慮只有對稱的時候要特別注意。

計算對稱的情況
dp[i] 表示左右各伸展 i 的對稱情況。
dp[i+1] += dp[i] //兩邊補上 1 x 2
dp[i+2] += dp[i]*2//兩邊補上 2x1 跟 2x2 兩種。

起始值要看奇偶數。

奇數要對稱中間一定會放一個 1x2
偶數則可以放三種，兩邊放 1x2, 或者跨越放 2x1, 2x2



#include <stdio.h>

int main() {
    int testcase;
    int i, j, k, n;
    int dp1[105] = {};
    dp1[0] = 1;
    for(i = 0; i < 105; i++) {
        dp1[i+2] += dp1[i]*2;
        dp1[i+1] += dp1[i];
    }
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        if(n&1) {
            int dp[100] = {};
            dp[1] = 1;
            dp[2] = 2;
            for(i = 1; i <= n/2; i++) {
                dp[i+1] += dp[i];
                dp[i+2] += dp[i]*2;
            }
            printf("%d\n", (dp1[n]+dp[(n-1)/2])/2);
        } else {
            int dp[100] = {};
            dp[1] = 3;
            dp[2] = 2;
            for(i = 1; i <= n/2; i++) {
                dp[i+1] += dp[i];
                dp[i+2] += dp[i]*2;
            }
            printf("%d\n", (dp1[n]+dp[n/2])/2);
        }
    }
    return 0;
}