d054 - 11310 - DELIVERY DEBACLE

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算用兩種蛋糕（1x1 正方形和 L 形蛋糕）填充 2xn 矩形有多少種不同的方法。

解題思路

這道題可以使用動態規劃來解決。定義 dp[i] 為填充 2xi 矩形的方法數。考慮填充 2xi 矩形的最後一列，可以有以下幾種情況：

1. 放置一個 1x1 的正方形蛋糕，則剩餘的矩形為 2x(i-1)，方法數為 dp[i-1]。
2. 放置兩個 1x1 的正方形蛋糕，則剩餘的矩形為 2x(i-2)，方法數為 dp[i-2]。
3. 放置一個 L 形蛋糕，則剩餘的矩形可以通過旋轉 L 形蛋糕得到不同的填充方式，總共有四種旋轉方式，但實際上只需要考慮兩種，因為另外兩種是這兩種的鏡像。此時，剩餘的矩形為 2x(i-2)，方法數為 dp[i-2]。
4. 放置兩個 L 形蛋糕，則剩餘的矩形為 2x(i-3)，方法數為 dp[i-3]。

因此，遞迴關係式為 dp[i] = dp[i-1] + dp[i-2] + 2*dp[i-2] + dp[i-3]，簡化為 dp[i] = dp[i-1] + (dp[i-2] << 2) + (dp[i-3] << 1)。

複雜度分析

• 時間複雜度: O(n)
• 空間複雜度: O(n)

程式碼

#include <stdio.h>
long long int dp[41]={1,1,5};
int main(){
	for(int i=3;i<41;i++)
		dp[i]=dp[i-1]+(dp[i-2]<<2)+(dp[i-3]<<1);
	int t,n;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		printf("%lld\n",dp[n]);
	}
}