b587 - 10918 - Tri Tiling

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算用 1x2 的地磚鋪滿 3xn 地面的方法數。n 的範圍是 0 到 30，輸入 -1 結束。

解題思路

這道題可以使用動態規劃來解決。我們可以定義 ans[i] 為鋪滿 3xi 地面的方法數。 當 n 為奇數時，由於 3xn 的面積為奇數，而 1x2 地磚的面積為偶數，因此不可能完全鋪滿，方法數為 0。 當 n 為偶數時，我們可以考慮最後兩塊地磚的擺放方式，建立遞迴關係。 ans[i] = ans[i-1] * 2 + ans[i-2] (當 i 為奇數) ans[i] = ans[i-2] + ans[i-1] (當 i 為偶數) 初始條件為 ans[0] = 1 和 ans[1] = 2。 程式碼中預先計算了 ans[0] 到 ans[30] 的值，然後根據輸入的 n 值輸出對應的結果。

複雜度分析

• 時間複雜度: O(n) (預計算 DP 表格) + O(1) (查詢) = O(n)
• 空間複雜度: O(n) (儲存 DP 表格)

程式碼

#include <iostream>
long long int ans[31]={1,2},n;
using namespace std; 
int main(){
	for(int i=2;i<31;++i)
		if(i%2)
			ans[i]=ans[i-1]*2+ans[i-2];
		else
			ans[i]=ans[i-2]+ans[i-1];
	while(cin >> n){
		if(n==-1)break;
		if(n%2)
			cout << "0\n";
		else
			cout << ans[n] << "\n";
	}
}