a388 - 00580 - Critical Mass

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算在 n 個桶子（U 或 L）的堆疊中，有多少種排列方式會導致至少連續三個 U 桶出現，從而引發危險。

解題思路

這道題可以使用動態規劃來解決。定義 dp[i][j] 表示使用 i 個桶子，且最後 j 個桶子不構成危險的方案數。其中 j 可以是 0, 1, 2，分別表示最後 0 個、1 個、2 個桶子不構成危險。

初始化：dp[1][0] = dp[1][1] = 1，表示一個桶子可以是 U 或 L。

遞推關係：

• dp[i][0]：表示第 i 個桶子是 L，則前 i-1 個桶子的方案數為 dp[i-1][0] + dp[i-1][1] + dp[i-1][2]。
• dp[i][1]：表示第 i 個桶子是 U，且前一個桶子不是 U，則前 i-1 個桶子的方案數為 dp[i-1][0]。
• dp[i][2]：表示第 i 個桶子是 U，且前一個桶子是 U，則前 i-1 個桶子的方案數為 dp[i-1][1]。

最終答案為 2^n - (dp[n][0] + dp[n][1] + dp[n][2])，即總方案數減去不構成危險的方案數。

複雜度分析

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

程式碼

#include <iostream>
using namespace std;
long long dp[35][3],n;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	dp[1][0]=dp[1][1]=1;//U,R
	for(int i=2;i<=30;++i){
		dp[i][0]+=dp[i-1][0]+dp[i-1][1]+dp[i-1][2];
		dp[i][1]+=dp[i-1][0];
		dp[i][2]+=dp[i-1][1];
		/*cout << i << " ";
		for(int j=0;j<3;++j){
			cout << dp[i][j] << " ";
		}
		cout << "\n";*/
	}
	while(cin >> n){
		if(n==0)break;
		cout << (1<<n)-(dp[n][0]+dp[n][1]+dp[n][2])<< "\n";
	}
}