d674 - 10192 - Vacation
題目描述
題目描述了兩個父母對旅行城市順序的建議，要求計算在盡可能滿足父母建議的情況下，最多可以訪問多少個城市。
解題思路
本題可以轉化為求兩個字串的最長公共子序列 (Longest Common Subsequence, LCS) 的問題。其中，兩個字串分別代表父母建議的旅行順序。LCS 的長度即為可以訪問的城市的最大數量。
程式使用動態規劃 (Dynamic Programming) 來計算 LCS。dp[i][j] 表示字串 a 的前 i 個字元和字串 b 的前 j 個字元的最長公共子序列的長度。
如果 a[i] 等於 b[j]，則 dp[i][j] = dp[i-1][j-1] + 1。
否則，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
複雜度分析
- 時間複雜度: O(n*m)，其中 n 和 m 分別是兩個字串的長度。
- 空間複雜度: O(n*m)，用於儲存
dp表格。
程式碼
#include <iostream>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int ca=0;
string a,b;
while(getline(cin,a)){
if(a=="#")break;
getline(cin,b);
cout << "Case #" << ++ca << ": you can visit at most ";
int al=a.length(),bl=b.length(),dp[al+1][bl+1];
a=' '+a;
b=' '+b;
for(int i=0;i<=al;++i)
dp[i][0]=0;
for(int j=0;j<=bl;++j)
dp[0][j]=0;
for(int i=1;i<=al;++i){
for(int j=1;j<=bl;++j){
if(a[i]==b[j])
dp[i][j]=dp[i-1][j-1]+1;
else
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
cout << dp[al][bl] << " cities.\n";
}
}