题解：P1439 【模板】最长公共子序列

_DATA_X_ · 2025-03-10 20:10:27 · 题解

本蒟蒻第一篇题解，可能有不清楚的地方，详细参考楼下dalao

思路：就是把LCS问题转换成LIS问题

先求出a数组每个数的位置，储存在数组c中，再求出b数组每个数在a数组中的位置，再根据位置数组进行LIS

AC code：

#include<bits/stdc++.h>//万能头文件
#define int long long//define:将int替换成long long
using namespace std;
const int N=100100;//数组长度
int a[N],b[N],c[N],dp[N];
int n,i; 
signed main(){//还原（main函数返回值只能为int类型）
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);//快读快写
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>a[i];
        c[a[i]]=i;//求出a数组的每个数的位置    
    }
    for(i=1;i<=n;i++) cin>>b[i];
    //求b数组的每个数在a数组的位置的LIS
    dp[1]=c[b[1]];//边界 
    //从第二个数开始讨论
    int len=1;
    int l,r,mid;
    for(i=2;i<=n;i++){
        //增加LIS的长度 
        if(c[b[i]]>dp[len]){
            len++;
            dp[len]=c[b[i]];
        }else{
            l=1;r=len;
            while(l<=r){
                mid=l+r>>1;
                if(c[b[i]]<=dp[mid]) r=mid-1;
                else l=mid+1;
            }
            dp[l]=c[b[i]];
        }
    } 
    cout<<len;
    return 0;//圆满结束！！！
} 

本蒟蒻第一篇题解，求过！！！