程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> Tri Tiling(hdu1143)

Tri Tiling(hdu1143)

編輯:關於C++

Tri Tiling

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2731 Accepted Submission(s): 1547


 

Problem Description In how many ways can you tile a 3xn rectangle with 2x1 dominoes? Here is a sample tiling of a 3x12 rectangle.

\

Input Input consists of several test cases followed by a line containing -1. Each test case is a line containing an integer 0 ≤ n ≤ 30.

Output For each test case, output one integer number giving the number of possible tilings.

Sample Input
2
8
12
-1

Sample Output
3
153
2131

Source University of Waterloo Local Contest 2005.09.24
思路:

1.標記和概念說明

f(n):其中的n即為題目中矩形的長,高固定位3,也即為題目中說的3xn中的n,f(n)表示當長為n時,所有的擺放方式的數量。分割線:一條豎直的線,這條線穿過題目中的矩形,將矩形一分為二,且這條線不能從磚的中間穿過,也 就是說只有磚的邊緣對齊的時候,才能穿過。

2.解題思想

2.1 對於每一種磚的擺放情況,可能有多條上面說的分割線,但是對於每一種情況,我們只需要所有分割線中最右邊的一條,我們記為L。也就是說在L的右邊的部分就是不可分割的了,但是左邊可能還是可以分割的。對於L的左邊我們繼續使用函數f即可,而右邊是需要我們研究的主要部分,因為右邊不能應用函數f。

2.2 不能應用函數f的原因是因為右邊不在可分割。對於長度為2的不可分割矩形的擺放方式有三種方式,對長度大於2的不可分割矩形的擺放方式有兩種方式。上一句話的理解也許需要你拿起筆在紙上畫一畫。

2.3 同時,考慮這樣的L可能在哪些位置?可能在從右邊數起的長度為2的位置,也有可能在長度為4的位置,……, 也有可能在長度為n的位置。當然,也只可能在上述的位置中,

因此有如下結果:

f(n)=f(n-2)*3+f(n-4)*2+...+f(2)*2+f(0)*2 ---- 表達式1

然後,將上式用n-2替換得: f(n-2)=f(n-4)*3+f(n-6)*2+...+f(2)*2+f(0)*2 ---- 表達式2

表達式1減去表達式2得: f(n)=4*f(n-2)-f(n-4)2.4 在利用上面的遞推公式時,我們需要兩個遞推的出口,即f(0) = 1, f(2) = 3.由上面的遞推公式也知道 不涉及當n為奇數的情況,當n為奇數時,直接為零。因為當n為奇數時,矩形的面積為奇數,但是不管我們使 用了多少塊磚,磚的總面積一定是個偶數,所以不存在任何的擺放形式。
 
 

這裡有一點我覺得比較坑。那就是F[0]=1;當n=0的時候為什麼是1 ???

 

#include
#define LL __int64
LL ans[35];
void init()
{
    ans[0]=1;
    ans[1]=ans[3]=0;
    ans[2]=3;ans[4]=11;
    for(int i=5;i<=30;i++)
    {
        if(i&1) ans[i]=0;
        else ans[i]=ans[i-2]*4-ans[i-4];
    }
}
int main()
{
    int n;
    init();
    while(scanf(%d,&n)!=EOF)
    {
        if(n==-1) break;
        printf(%I64d
,ans[n]);
    }
    return 0;
}

 


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved