Time Limit: 2000/1000 MS (java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 50253 Accepted Submission(s): 24237
在2×n的一個長方形方格中,用一個1× 2的骨牌鋪滿方格,輸入n ,輸出鋪放方案的總數(shù). 例如n=3時,為2× 3方格，骨牌的鋪放方案有三種,如下圖：
Input
輸入數(shù)據(jù)由多行組成，每行包含一個整數(shù)n,表示該測試實(shí)例的長方形方格的規(guī)格是2×n (0 < n < =5 0)。
Output
對于每個測試實(shí)例，請輸出鋪放方案的總數(shù)，每個實(shí)例的輸出占一行。
Sample Input
1 3 2
Sample Output
1 3 2
本題思路： 一開始用dfs做，結(jié)果自然的超時了。于是發(fā)現(xiàn)原來是個遞推題。 過程如下： 每當(dāng)增加一個空位時如果豎著放的話，方法為f[n-1]， 如果橫著放，就需要兩個，把第n-1和第n 個橫著放，方法為f[n-2] 所以遞推出公式f[n]=f[n-1]+f[n-2]
#include<stdio.h>#include<stdlib.h>int main(){ long long f[52]={1,1,2,3}; int num,i; for(i=4;i<=50;i++) f[i]=f[i-1]+f[i-2]; while(~scanf("%d",&num)){ printf("%I64d/n",f[num]); } return 0;}新聞熱點(diǎn)
疑難解答
