ZeroJudge 解題筆記：a133. 10066 - The Twin Towers

作者：王一哲
日期：2025年12月19日


ZeroJudge 題目連結：a133. 10066 - The Twin Towers

解題想法

這題考最長共同子序列 (longest common subsequence, LCS)，只要找長度，不需要找 LCS 的內容。寫法有兩種，假設兩筆資料 a、b 的長度分別為 n、m，可以用一個 $(n+1) \times (m+1)$ 的二維陣列儲存動態規劃資料，$dp[i][j]$ 代表比較到 $a[i-1]$ 與 $b[i-1]$ 時 LCS 的長度；也可以用兩個陣列儲存資料，用滾動陣列節省記憶體。

Python 程式碼

使用時間約為 1.4 s，記憶體約為 4 MB，通過測試。

import sys

ca = 0
for line in sys.stdin:
    n, m = map(int, line.split())
    if n == 0 and m == 0: break
    ca += 1
    print(f"Twin Towers #{ca:d}")
    a = tuple(map(int, sys.stdin.readline().split()))
    b = tuple(map(int, sys.stdin.readline().split()))
    dp = [[0]*(m+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, m+1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    print(f"Number of Tiles : {dp[-1][-1]:d}\n")

使用時間約為 1.1 s，記憶體約為 3.8 MB，通過測試。

import sys

ca = 0
for line in sys.stdin:
    n, m = map(int, line.split())
    if n == 0 and m == 0: break
    ca += 1
    print(f"Twin Towers #{ca:d}")
    a = tuple(map(int, sys.stdin.readline().split()))
    b = tuple(map(int, sys.stdin.readline().split()))
    d, p = [0]*(m+1), [0]*(m+1)
    for i in range(1, n+1):
        for j in range(1, m+1):
            if a[i-1] == b[j-1]:
                d[j] = p[j-1] + 1
            else:
                d[j] = max(p[j], d[j-1])
        d, p = p, d
    print(f"Number of Tiles : {p[-1]:d}\n")

C++ 程式碼

使用時間約為 3 ms，記憶體約為 348 kB，通過測試。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int ca = 0, n, m;
    while(cin >> n >> m) {
        if (n == 0 && m == 0) break;
        ca++;
        cout << "Twin Towers #" << ca << "\n";
        vector<int> a (n+1, 0), b (m+1, 0);
        vector<vector<int>> dp (n+1, vector<int> (m+1, 0));
        for(int i=0; i<n; i++) cin >> a[i];
        for(int i=0; i<m; i++) cin >> b[i];
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                if (a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        cout << "Number of Tiles : " << dp[n][m] << "\n";
    }
    return 0;
}

使用時間約為 9 ms，記憶體約為 352 kB，通過測試。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int ca = 0, n, m;
    while(cin >> n >> m) {
        if (n == 0 && m == 0) break;
        ca++;
        cout << "Twin Towers #" << ca << "\n";
        vector<int> a (n+1, 0), b (m+1, 0), d (m+1, 0), p (m+1, 0);
        for(int i=1; i<=n; i++) cin >> a[i];
        for(int i=1; i<=m; i++) cin >> b[i];
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                if (a[i] == b[j]) d[j] = p[j-1] + 1;
                else d[j] = max(p[j], d[j-1]);
            }
            d.swap(p);
        }
        cout << "Number of Tiles : " << p.back() << "\n";
    }
    return 0;
}