【模板】最长公共子序列 (【DP or 贪心】板子)

【模板】最长公共子序列

题目描述

给出 $1,2,\dots ,n$ 的两个排列 $P_1$ 和 $P_2$ ，求它们的最长公共子序列。

输入格式

第一行是一个数 $n$。

接下来两行，每行为 $n$ 个数，为自然数 $1,2,\dots ,n$ 的一个排列。

输出格式

一个数，即最长公共子序列的长度。

样例 #1

样例输入 #1

5 
3 2 1 4 5
1 2 3 4 5

样例输出 #1

3

提示

• 对于 $50\%$ 的数据， $n\le 10^3$；
• 对于 $100\%$ 的数据， $n\le 10^5$。

DP ($o(n^2)$)

模板

#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();
}

贪心 ($o(nlogn)$)

模板

#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();
}