e881 - Q2 極限運動
題目描述
題目要求計算從起點到終點的路線數量。可以每次走 1 到 m 步，但有些點是禁止經過的。最終輸出到達終點的路線數量，由於數量可能很大，因此以字串形式輸出。
解題思路
本題可以使用動態規劃 (Dynamic Programming) 解決。dp[i] 表示到達第 i 個位置的路線數量。初始化 dp[0] 為 "1"，表示從起點出發只有一條路線。然後，從 i = 0 到 n 遍歷每個位置，如果 dp[i] 不為 "-1" (表示該位置可以到達)，則可以從該位置向前走 1 到 m 步。對於每個可以到達的位置 i + j (其中 1 <= j <= m)，將 dp[i] 加到 dp[i + j] 上。注意，由於路線數量可能很大，需要使用字串來儲存和計算。禁止經過的位置用 "-1" 表示，在計算時跳過這些位置。
複雜度分析
- 時間複雜度: O(n * m * k)，其中 n 是終點位置，m 是最大步數，k 是字串加法的平均長度。
- 空間複雜度: O(n)，用於儲存 dp 陣列。
程式碼
#include <iostream>
using namespace std;
int n,m,d,t;
string dp[1051]={"1"};
string add(string a,string b){
int tmp[1001]={0},al=a.length(),bl=b.length();
string c;
for(int i=0;i<al;++i)tmp[al-i-1]+=a[i]-'0';
for(int i=0;i<bl;++i)tmp[bl-i-1]+=b[i]-'0';
for(int i=0;i<1000;++i)
if(tmp[i]>9){
++tmp[i+1];
tmp[i]-=10;
}
for(int i=1000;i>=0;--i)
if(tmp[i]){
al=i;
break;
}
for(int i=al;i>=0;--i)c+=tmp[i]+'0';
return c;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n >> m >> d;
while(d--){
cin >> t;
dp[t]="-1";
}
for(int i=0;i<=n;++i){
if(dp[i]=="-1")continue;
for(int j=1;j<=m&&i+j<=n;++j){
if(dp[i+j]=="-1")continue;
dp[i+j]=add(dp[i+j],dp[i]);
}
}
cout << dp[n];
}