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

题目连接:https://www.luogu.com.cn/problem/P1439

 

思路:

因为题目数据较大,不能用一般的最长相同子序列来求,所以可以将序列1中的编号放到序列2中,在两个序列中都递增的子序列就是最长相同的子序列,所以题目就转化为求转化过的bi串的最长上升子序列就好了。

 

代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N],b[N],n,mp[N] = {0},id[N] = {0};
vector <int> vc;
int main(void)
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),mp[ a[i] ] = i;
    for(int i=1;i<=n;i++) scanf("%d",&b[i]),b[i] = mp[ b[i] ];
    int ans = 1;
    for(int i=1;i<=n;i++)
    {
        int pos = lower_bound(vc.begin(),vc.end(),b[i]) - vc.begin();
        int sz = vc.size();
        if(sz == pos){
            vc.push_back(b[i]);
            sz++;
        }
        else{
            vc[ pos ] = b[i];
        }
        ans = max(ans,sz);
    }
    printf("%d\n",ans);
    return 0;
}

 

P1439 【模板】最长公共子序列(LIS)P1439 【模板】最长公共子序列(LIS) WA掘机 发布了438 篇原创文章 · 获赞 16 · 访问量 3万+ 私信 关注
上一篇:洛谷 P1439 【模板】最长公共子序列(LCS、LIS)


下一篇:LIS是什么?【质量控制】