題目描述

給出兩個長度為 n 的整數(shù)序列，求它們的最長公共子序列（LCS）的長度，保證第一個序列中所有元素都不重復(fù)。

注意：
第一個序列中的所有元素均不重復(fù)。
第二個序列中可能有重復(fù)元素。
一個序列中的某些元素可能不在另一個序列中出現(xiàn)。

輸入樣例

5
2 1 3 8 7
2 9 3 4 5

輸入樣例

2

數(shù)據(jù)范圍

1 ≤ n ≤ 1 0 6 1≤n≤10^6 1≤n≤106, 序列內(nèi)元素取值范圍 [ 1 , 1 0 6 ] [1,10^6] [1,106]

分析

此題的數(shù)據(jù)量達(dá)到了1e6故不能用傳統(tǒng)的$o(n^2)$的dp做法，需考慮$o(nlogn)$的做法。
由于第一個序列中元素不重復(fù)，這是一個典型的最長公共子序列轉(zhuǎn)換為最長上升子序列問題。

最長上升子序列求法 $O(nlogn)$

首先我們看看最長公共子序列的求解過程是什么樣子的？

A: 2 1 3 8 7
B: 2 9 3 4 5

ans = {2, 3};

就是從B中按照下標(biāo)從小到大的順序（從左至右）去A中找相同的數(shù)字，且在A中數(shù)字的下標(biāo)也需要是遞增的(也需要從左至右)

我們用另一種方式模擬這個過程

① 我們先將A中的數(shù)字和下標(biāo)存儲在idx數(shù)組中idx[key] = value,key 對應(yīng)的是A中的值，value對應(yīng)的是A中元素值對應(yīng)的下標(biāo)；

② 再按照坐標(biāo)序遍歷B中的元素，找到其在A中的位置idx[key], 找到一個我們就處理這個元素的下標(biāo)到f數(shù)組中，將f數(shù)組維護為遞增數(shù)組（剛剛我們說到A，B的子序列下標(biāo)都需要是遞增的）;

f 數(shù)組維護的是B數(shù)組元素在A數(shù)組元素中的下標(biāo)

時間復(fù)雜度

$O(nlogn)$文章來源地址http://www.zghlxwxcb.cn/news/detail-705854.html

C++ 代碼

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 7;

int idx[N], f[N];
int cnt;
int n;

int find(int x) {
    int l = 0, r = cnt;
    while (l < r) {
        int mid = l + r >> 1;
        if (f[mid] >= x) r = mid;
        else l = mid + 1;
    }
    
    return l;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n;
    memset(idx, -1, sizeof idx);
    
    for (int i = 1; i <= n; i ++ ) {
        int x;
        cin >> x;
        idx[x] = i;     // 記錄數(shù)組中每個值的下標(biāo)是多少
    }
    
    
    for (int i = 1; i <= n; i ++ ) {
        int x;
        cin >> x;
        
        int k = idx[x];
        if (k == -1) continue;
        
        if (k > f[cnt]) f[ ++ cnt ] = k;    // 如果當(dāng)前下標(biāo)大于f數(shù)組末尾元素下標(biāo)就直接加入f數(shù)組
        else {
            int p = find(k);    // 找到大于等于k的第一個數(shù)的下標(biāo)
            f[p] = k;           // 將下標(biāo)的對應(yīng)值替換掉
        }
    }
    
    cout << cnt << endl;
    return 0;
}

到了這里，關(guān)于最長公共子序列（上海交通大學(xué)考研機試題）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！