- #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;
- }
---------------------------------------------------------
這是一個「最長公共子序列（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） |
