最长公共子序列

题目描述

给定序列 $A =(a_1, a_2,\ldots , a_n)$ 和 $B =(b_1, b_2,\ldots , b_m)$ ，求它们的最长公共子序列

子序列的定义参考题目 最长上升子序列

输入格式

第一行两个整数 $n, m$ 代表序列 $A,B$ 的长度

第二行是 $n$ 个由空格隔开的整数，代表 $a_1, a_2,\ldots , a_n$

第三行是 $m$ 个由空格隔开的整数，代表 $b_1,b_2,\ldots , b_m$

输出格式

输出一个整数，代表最长公共子序列的长度

测试样例

样例输入

5 5
3 2 1 4 5
1 2 3 4 5

样例输出

3

数据规模

对于 $100 \%$ 的数据，$1 \le n, m \le 5000, 1\le a_i, b_i\le10^4$

#include <bits/stdc++.h>
using namespace std;
#define N 5005
int c[N + 1][N + 1];
int lcs(deque<int>& x, deque<int>& y) {
    int m = x.size(), n = y.size(), maxl = 0;
    x.emplace_front(-1), y.emplace_front(-1);
    memset(c, 0, sizeof(c));
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (x[i] == y[j])
                c[i][j] = c[i - 1][j - 1] + 1;
            else
                c[i][j] = max(c[i - 1][j], c[i][j - 1]);
            maxl = max(maxl, c[i][j]);
        }
    }
    return maxl;
}

int main() {
    int n, m, ta, tb;
    deque<int> a, b;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        scanf(" %d", &ta), a.emplace_back(ta);
    for (int i = 1; i <= m; ++i)
        scanf(" %d", &tb), b.emplace_back(tb);
    cout << lcs(a, b);
}