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

hotarugali

发布于 2022-03-17 21:24:04

5120

发布于 2022-03-17 21:24:04

文章被收录于专栏：hotarugaliの技术分享hotarugaliの技术分享

1. 题目

题目链接：P1439「【模板】最长公共子序列」。

题目描述

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

输入格式

第一行是一个数 n 。

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

输出格式

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

输入输出样例

输入 #1

5 
3 2 1 4 5
1 2 3 4 5

输出 #1

说明 / 提示

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

2. 题解

分析

这是一道 LCS 的模板题，但是如果只用朴素的动态规划来解，复杂度是 O(n^2) ，结果终究会 TLE。和 LCS 类似的是 LIS，然而 LIS 有 O(n \log{n}) 的解法，幸运的是部分 LCS 问题可以用 LIS 来解。

在 LCS 中，两个序列中的元素仅表示一种符号，用来判定是否相等的符号，对于符号背后具体的数值对 LCS 的结果并没有影响。
在 LIS 中，是需要考虑序列元素的数值大小关系的。

若 LCS 的两个序列中的其中一个元素互异，则可以用 LIS 来解。在此类 LCS 中，不防假设序列A 中元素是互异的，设序列 A 的长度为 n ，则我们可以考虑将 A 的元素按照出现顺序依次映射到 1 \ldots n 上，从而得到 A 中元素与数值的一一对应关系。然后根据 A 元素的映射表，来计算序列 B

元素对应的映射值；对于在 B 中存在而不在 A 中存在的元素，直接舍弃即可，因为它们必然不会出现在 LCS 中。如此，映射完 B 得到的数值序列设为 C ，其长度为m 。则此时只需要计算序列 C 的 LIS 即可。这是因为序列 A 映射后的序列是一个递增的数值序列，因此 A 和 C 的公共子序列也是递增子序列，最长公共子序列也是最长递增子序列，即序列 C 的最长递增子序列。

针对这道题而言，由于两个序列都是 1 \ldots n 的排列，因此可以转为 LIS 问题来求解。

代码

#include <bits/stdc++.h>
using namespace std;

// 最长递增子序列
struct LIS{
    #ifndef _LIS_
    #define ll int 
    #define MAXN 100005
    #endif 
    ll n;
    ll A[MAXN];
    LIS(): n(0) {}
    // 二分+栈求 LIS 长度
    // 复杂度 O(nlogn)
    ll length() {
        ll cntn = n;
        ll *seqa = A;
        vector <ll> lis;
        lis.push_back(seqa[0]);
        for(ll i = 1; i < cntn; ++i) {
            if(seqa[i] > lis.back()) {
                lis.push_back(seqa[i]);
            } else {
                ll pos = lower_bound(lis.begin(), lis.end(), seqa[i]) - lis.begin();
                lis[pos] = min(lis[pos], seqa[i]);
            }
        }
        return lis.size();
    }
};

int main()
{
    int n;
    int P[MAXN];
    LIS lis;
    scanf("%d", &n);
    lis.n = n;
    for(int i = 0; i < n; ++i) {
        int a;
        scanf("%d", &a);
        P[a] = i; 
    }
    for(int i = 0; i < n; ++i) {
        int b;
        scanf("%d", &b);
        lis.A[i] = P[b];
    }
    printf("%d\n", lis.length());
    return 0;
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2021-01-26，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度