a133 - 10066 - The Twin Towers
題目描述
題目要求計算兩個塔（由磁磚組成）之間最長共同子序列的長度，代表可以保留的最大磁磚數，使得兩座塔的形狀大小相同，且維持原始順序。
解題思路
本題可以轉化為求兩個序列的最長公共子序列 (Longest Common Subsequence, LCS) 問題。塔的磁磚半徑序列可以視為兩個字串，LCS 的長度即為兩座塔可以保留的最大磁磚數。
使用動態規劃 (Dynamic Programming) 解決 LCS 問題。定義 len[i][j] 為第一座塔的前 i 個磁磚和第二座塔的前 j 個磁磚的最長公共子序列的長度。
- 如果
c[i] == d[j]，則len[i][j] = len[i-1][j-1] + 1。 - 否則，
len[i][j] = max(len[i-1][j], len[i][j-1])。 最終結果為len[a][b]，其中a和b分別是兩座塔的磁磚數。
複雜度分析
- 時間複雜度: O(n*m)，其中 n 和 m 分別是兩座塔的磁磚數。因為需要遍歷一個 n x m 的矩陣。
- 空間複雜度: O(n*m)，因為需要一個 n x m 的矩陣來儲存中間結果。
程式碼
#include <iostream>
using namespace std;
int main(){
int a,b,ca=0;
while(cin >> a >> b){
if(a==0&&b==0)break;
++ca;
int c[a+1],d[b+1],li=0;
int len[a+1][b+1];
for(int i=1;i<=a;++i)
cin >> c[i];
for(int i=1;i<=b;++i)
cin >> d[i];
for (int i=0; i<=a; ++i)
len[i][0] = 0;
for (int i=0; i<=b; ++i)
len[0][i] = 0;
for(int i=1;i<=a;++i){
for(int j=1;j<=b;++j){
if(c[i]==d[j])
len[i][j]=len[i-1][j-1]+1;
else
len[i][j]=max(len[i-1][j],len[i][j-1]);
}
}
cout << "Twin Towers #"<< ca << "\nNumber of Tiles : " << len[a][b] << "\n\n";
}
}