c914 - 導盲磚

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算在寬度為 2，長度為 n 的區域內，使用 2x1 的矩形磚和 1x1 的正方形磚鋪設的不同方式數量。

解題思路

這道題目可以利用動態規劃來解決。定義 a[n] 為長度為 n 時，完全由 2x1 矩形磚和 1x1 正方形磚鋪滿的方案數。 觀察可以發現，a[n] 的計算可以基於前幾個狀態的值。 a[0] 和 a[1] 的值可以直接定義。 a[2] 可以由兩個 2x1 矩形磚或四個 1x1 正方形磚組成。 對於 a[n]，可以考慮最後一個位置的鋪設方式：

1. 如果最後一個位置是 2x1 的矩形磚，則前 n-1 個位置的鋪設方式有 a[n-1] 種。
2. 如果最後一個位置是兩個 1x1 的正方形磚，則前 n-2 個位置的鋪設方式有 a[n-2] 種。
3. 如果最後一個位置是 1x1 的正方形磚，則前 n-1 個位置的鋪設方式有 b[n-1] 種。
4. 如果最後一個位置是 2x1 的矩形磚，則前 n-2 個位置的鋪設方式有 b[n-2] 種。

其中 b[n] 表示長度為 n 時，第一列和第二列的鋪設方式不同。 b[n] = a[n-1] * 2 + b[n-1] a[n] = a[n-1] * 2 + a[n-2] + b[n-1]

程式碼中，a[i] 和 b[i] 預先計算好，然後根據輸入的 n 值直接輸出 a[n]。

複雜度分析

• 時間複雜度: O(31) + O(t) (預計算 a 和 b 陣列的時間複雜度是常數，讀取輸入和輸出結果的時間複雜度是 O(t)，其中 t 是測試案例的數量)
• 空間複雜度: O(31) (使用兩個大小為 31 的陣列 a 和 b)

程式碼

#include <iostream>
using namespace std;
long long int a[31]={1,2},b[31]={1,2},n,t;
int main(){
	for(int i=2;i<31;++i){
		b[i]=a[i-1]*2+b[i-1];
		a[i]=a[i-1]*2+a[i-2]+b[i-1];
	}
	cin >> t;
	while(t--){
		cin >> n;
		cout << a[n] << '\n';
	}
}