d702 - SOS
題目描述
題目要求計算在 n 秒內，使用 1 秒短音和 2 秒長音，且最後一個音符恰好在第 n 秒結束的吹哨方式數量。
解題思路
這道題可以使用動態規劃來解決。定義 dp[i] 為在 i 秒內吹哨的方式數量。我們可以通過考慮最後一個音符是短音還是長音來建立遞迴關係。
- 如果最後一個音符是短音，則前
i-1秒內必須有dp[i-1]種吹法。 - 如果最後一個音符是長音，則前
i-2秒內必須有dp[i-2]種吹法。
因此，dp[i] = dp[i-1] + dp[i-2]。 初始條件為 dp[0] = 1 (表示沒有吹哨的方式) 和 dp[1] = 1 (只有一種吹法，即一個短音)。
程式碼中，dp 陣列儲存了 dp[i] 的值。程式從 dp[3] 開始計算，直到 dp[1000]。然後，對於每個輸入 n，程式輸出 dp[n]。
程式碼使用字串來表示大數，並定義了 add 函數來執行字串加法。這是因為題目中 n 的範圍可能導致結果超出整數的表示範圍。
複雜度分析
- 時間複雜度: O(n)
- 空間複雜度: O(n)
程式碼
#include <iostream>
using namespace std;
string dp[1004]={"1","1","1"};
inline string add(string a,string b){
string sum;
int aa[200]={0},al=a.length(),bl=b.length(),i;
for(i=0;i<al;++i)
aa[i]=a[al-i-1]-48;
for(i=0;i<bl;++i){
aa[i]+=b[bl-i-1]-48;
if(aa[i]>9){
aa[i]-=10;
++aa[i+1];
}
}
if(!aa[al])--al;
for(i=0;i<=al;++i)
sum+=aa[al-i]+48;
return sum;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
for(int i=3;i<=1000;++i)
dp[i]="0";
for(int i=1;i<=1000;++i){
dp[i+2]=add(dp[i],dp[i+2]);
dp[i+3]=add(dp[i],dp[i+3]);
}
int n;
while(cin >> n)
cout << dp[n] << "\n";
}