d916 - 4. 高空煙火時間限制

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算在 N 個施放點上，兩個彩色煙火之間至少間隔 M 個單色煙火的煙火施放方式數量，並輸出結果除以 10000 的餘數。

解題思路

本題可以使用動態規劃來解決。定義 dp[i][0] 表示在前 i 個施放點中，第 i 個施放點為單色煙火的方案數，dp[i][1] 表示在前 i 個施放點中，第 i 個施放點為彩色煙火的方案數。

初始化 dp[1][0] = dp[1][1] = 1，表示只有一個施放點時，無論是單色還是彩色煙火，都只有一種方案。

對於 i > 1，dp[i][0] 可以由前一個施放點是單色或彩色的方案數累加得到，即 dp[i][0] = dp[i-1][0] + dp[i-1][1]。

dp[i][1] 的計算需要考慮兩個彩色煙火之間至少間隔 M 個單色煙火的限制。如果第 i 個施放點是彩色煙火，那麼第 i-1 個施放點可以是單色或彩色。如果第 i-1 個施放點是單色，則 dp[i][1] 可以直接加上 dp[i-1][0]。如果第 i-1 個施放點是彩色，則第 i-M-1 個施放點必須是單色或彩色，因此 dp[i][1] 加上 dp[i-M-1][0] 和 dp[i-M-1][1]。但由於題目要求兩個彩色煙火之間至少間隔 M 個單色煙火，所以需要減去 dp[i-M-1][1]，避免重複計算。

最後，答案是 (dp[n][0] + dp[n][1]) % 10000。

複雜度分析

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

程式碼

#include <iostream>
using namespace std;
int dp[3005][2],n,m;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n >> m;
	dp[1][0]=dp[1][1]=1;
	for(int i=2;i<=n;++i){
		dp[i][0]+=dp[i-1][0]+dp[i-1][1];
		dp[i][1]=1;
		if(i>m+1){
			dp[i][1]+=dp[i-m-1][1];
			dp[i][1]+=dp[i-m-1][0]-1;
		}
		dp[i][0]%=10000;
		dp[i][1]%=10000;
		//cout << dp[i][0] << " " << dp[i][1] << "\n";
	}
	cout << (dp[n][0]+dp[n][1])%10000;
}