P1439 【模板】最长公共子序列

题目

P1439 【模板】最长公共子序列

算法标签: 动态规划, 线性$dp$

思路

求两个字符串的最长公共子序列, 设计状态表示$f[i][j]$, 代表第一个字符串的前$i$个字符, 第二个字符串的前$j$个字符组成的最长公共子序列的长度, 对于当前字符$s_1[i]$和$s_2[j]$如果两个相等直接从上一个状态转移$f[i-1][j-1]+1$, 但是如果两个字符不等, 就要看$f[i-1][j]$或者$f[i][j-1]$

$O(n^2)$写法

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;

int n, a[N], b[N];
int f[N][N];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> b[i];

    for (int i = 1; i <= n; ++i) {
   
        for (int j = 1; j <= n; ++j) {
   
            if (a[i] != b[j]) f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            else f[i][j] = f[i - 1][j - 1] + 1;
        }
    }

    cout << f[n][n] << "\n";
    return 0;
}

*$O(n\log n)$写法

#include<iostream>
#include<cstdio>

using namespace std;

int a[100001], b[100001], map[100001], f[100001];

int main() {
   
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
   
        scanf("%d", &a[i]);
        map[a[i]] = i;
    }
    for (int i = 1; i <= n; i++) {
   
        scanf("%d", &b[i]);
        f[i] = 0x7fffffff;
    }
    int len = 0;
    f[0] = 0;
    for (int i = 1; i <= n; i++) {
   
        int l = 0, r = len, mid;
        if (map[b[i]] > f[len]) f[++len] = map[b[i]];
        else {
   
            while (l < r) {
   
                mid = (l + r) / 2;
                if (f[mid] > map[b[i]]) r = mid;
                else l = mid + 1;
            }
            f[l] = min(map[b[i]], f[l]);
        }
    }
    cout << len;
    return 0
}