標題:
資料結構 503 雙子星塔
[打印本頁]
作者:
may
時間:
4 天前 17:19
標題:
資料結構 503 雙子星塔
資料結構 503 雙子星塔
1. 題目說明：
請依下列題意進行作答，使輸出值符合題意要求。
2. 設計說明：
(1) 在某個上古文明國家的境內有兩座形狀不同的塔，但共同點是兩座塔都是由大小不一的圓瓦堆砌起來的，這些圓瓦的高度相同且半徑均為整數。因此，儘管兩座塔的形狀雖然不一樣，卻包含了許多半徑相同的圓瓦。
[attach]20855[/attach]
(2) 大約在雙塔啟用後的一千年，這個國家的國王下令工匠移除部分圓瓦來讓雙塔的形狀相同，同時盡可能地維持最大高度，塔的高度就是圓瓦的數目（請注意新塔上的圓瓦順序應該和原先的順序相同），也因為兩座新塔的形狀完全一樣，所以國王將改建後的雙塔稱為「雙子星塔」。
(3) 現在給定兩座塔的形狀描述，請寫一個程式去計算出改建後的雙子星塔的最大高度。舉例：下圖兩塔改建後的圓瓦半徑從上到下，依序為15、10、15、20，高度為4。
雙子星塔
3. 輸入輸出：
輸入說明
第 1 列：輸入兩個介於 1~100 之間的正整數 a 和 b，分別表示兩座塔各自的圓瓦數目，整數間使用半形空白間隔。
第 2 列：輸入 a 個正整數，代表第一座塔從上到下每片圓瓦的半徑，整數間使用半形空白間隔。
第 3 列：輸入 b 個正整數，代表第二座塔從上到下每片圓瓦的半徑，整數間使用半形空白間隔。
（圓瓦半徑皆小於100）
輸出說明
改建後的最大高度。
範例輸入1
7 6
20 15 10 15 25 20 15
15 25 10 20 15 20
範例輸出1
4
範例輸入2
8 9
10 20 20 10 20 10 20 10
20 10 20 10 10 20 10 10 20
範例輸出2
6
作者:
may
時間:
4 天前 17:34
#include <bits/stdc++.h>
//#include <iostream>
//#include <vector>
using namespace std;
int longestCommonSubsequence(vector<int>& tower1, vector<int>& tower2) {
int a = tower1.size(), b = tower2.size();
vector<vector<int>> dp(a + 1, vector<int>(b + 1, 0));
for (int i = 1; i <= a; i++) {
for (int j = 1; j <= b; j++) {
if (tower1[i - 1] == tower2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[a][b];
}
int main() {
int a, b;
cin >> a >> b;
vector<int> tower1(a), tower2(b);
for (int i = 0; i < a; i++) cin >> tower1[i];
for (int i = 0; i < b; i++) cin >> tower2[i];
cout << longestCommonSubsequence(tower1, tower2) << endl;
return 0;
}
複製代碼
回復
1#
may
---------------------------------------------------------
這是一個「最長公共子序列（LCS）」的變形問題，需要在兩座塔的圓瓦排列中找出相同順序的最長子序列。
解題思路
輸入處理：
讀取兩座塔的圓瓦數量 a 和 b。
讀取兩個長度分別為 a 和 b 的陣列，代表兩座塔的圓瓦排列。
求解最長公共子序列（LCS）：
建立一個 dp 陣列，dp
[j] 代表第一座塔的前 i 個圓瓦與第二座塔的前 j 個圓瓦的最長公共子序列長度。
如果 tower1[i-1] == tower2[j-1]，則 dp
[j] = dp[i-1][j-1] + 1。
否則，dp
[j] = max(dp[i-1][j], dp
[j-1])。
最終 dp[a]
即為改建後雙塔的最大高度。
------------------------------------------------------------
讀取輸入：
先讀取兩座塔的圓瓦數量 a 和 b。
接著讀取兩座塔的圓瓦數列，儲存在 vector<int> 陣列中。
動態規劃計算 LCS：
使用 dp 陣列來儲存已計算的 LCS 值，避免重複計算。
透過兩層迴圈遍歷 dp 陣列，逐步找到最長的相同子序列。
輸出結果：
dp[a]
即為雙塔改建後的最大高度，最後輸出該值。
時間複雜度
O(a * b)，適用於 a, b ≤ 100 的情況，運算速度可接受。
-------------------------------------------------------------
測資
測試資料00
輸入：
7 6
20 15 10 15 25 20 15
15 25 10 20 15 20
預期輸出：
4
測試資料 01
輸入：
8 9
10 20 20 10 20 10 20 10
20 10 20 10 10 20 10 10 20
預期輸出：
6
測試資料02
輸入：
5 5
1 2 3 4 5
5 4 3 2 1
預期輸出：
1
（只有單一個數字可以匹配）
測試資料 03
輸入：
6 7
5 10 15 20 25 30
5 10 15 20 25 30 35
預期輸出：
6
（所有圓瓦都可以匹配）
測試資料04
輸入：
10 10
1 3 5 7 9 11 13 15 17 19
2 4 6 8 10 12 14 16 18 20
預期輸出：
0
（沒有一個圓瓦匹配）
這些測資涵蓋不同的情境，如：
部分相符（測試 1 & 2）
完全相反順序（測試 3）
完全匹配（測試 4）
完全不匹配（測試 5）
作者:
may
時間:
4 天前 17:49
標題:
練習網址
回復
1#
may
最長公共子序列解說
https://www.youtube.com/watch?v=WKzV8AthfmM
最長公共子序列練習
https://alchemist-al.com/algorithms/longest-common-subsequence
歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://seed.istak.org.tw/)
Powered by Discuz! 7.2
