[template] longest common subsequence ([DP or greedy] board)

【 Templates 】 Longest common subsequence

Title Description

give $1,2,\dots ,n$ Two permutations of $P_1$ and $P_2$ , Find their longest common subsequence .

Input format

The first line is a number $n$.

The next two lines , Every act $n$ Number , For natural Numbers $1,2,\dots ,n$ An arrangement of .

Output format

a number , That is, the length of the longest common subsequence .

Examples #1

The sample input #1

5 
3 2 1 4 5
1 2 3 4 5

Sample output #1

3

Tips

• about $50\%$ The data of , $n\le 10^3$;
• about $100\%$ The data of , $n\le 10^5$.

DP ($o(n^2)$)

Templates

#include <bits/stdc++.h>
#define buff                     \
    ios::sync_with_stdio(false); \
    cin.tie(0);
//#define int long long
using namespace std;
const int N = 1e3 + 9;
int n;
int s1[N], s2[N];
int dp[N][N];
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> s1[i];
    for (int i = 1; i <= n; i++)
        cin >> s2[i];

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            if (s1[i] == s2[j])
                dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
        }
    }
    cout << dp[n][n] << '\n';
}
int main()
{
    solve();
}

greedy ($o(nlogn)$)

Templates

#include <bits/stdc++.h>
#define buff                     \
    ios::sync_with_stdio(false); \
    cin.tie(0);
//#define int long long
using namespace std;
const int N = 1e5 + 9;
int n;
int s[N];
int q[N];
void solve()
{
    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        int t;
        cin >> t;
        s[t] = i;
    }
    memset(q, 0x3f, sizeof q);
    for (int i = 1; i <= n; i++)
    {
        int t;
        cin >> t;
        int x = s[t];
        *lower_bound(q + 1, q + 1 + n, x) = x;
    }

    cout << lower_bound(q + 1, q + 1 + n, q[0]) - q - 1 << '\n';
}
int main()
{
    solve();
}