蒟蒻求解

qujunhao @ 2024-09-13 18:32:40

by qujunhao @ 2024-09-13 18:33:08

闭关注

by XYstarabyss @ 2024-10-03 15:50:10

#include <iostream>
using namespace std;
#define f(n,m,i) for (int i = n;i <= m;i++)
#define fc(n,m,i) for (int i = n;i >= m;i--)
#define oo 1e9 

int n,a[100001],b[100001];
int dp[100001];//记录当前最长公共子序列的元素 
int map[100001];//记录第一个排列中各元素的顺序 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //硬核快读

    cin >> n;

    f(1,n,i){
        dp[i] = 0x7fffffff;
        //初始化dp数组 

        cin >> a[i];//输入第一个排列 

        map[a[i]] = i;
        //记录第一个排列中各元素的顺序 
    }
    f(1,n,i){
        cin >> b[i];//输入第二个排列 
    }
    dp[0] = 0;
    int len = 0;//记录当前已知最长公共子序列的长度 
    f(1,n,i){//遍历第二个排列 
        int l = 0,r = len,mid;
        //二分 
        if (map[b[i]] > dp[len]){
            //如果有比当前最长公共子序列中下标最大的还大公共元素对 
            dp[++len] = map[b[i]];
            //将这个公共元素对加入最长公共子序列 
        }
        else{
            //否则找一下这个公共元素对排在当前最长公共子序列的什么地方 
            while (l < r){
                mid = (l + r) / 2;
                if (dp[mid] > map[b[i]]){
                    r = mid;
                }
                else    l = mid + 1;
            }
            dp[l] = min(map[b[i]],dp[l]);
            //比一比看一下最长公共子序列的这个地方用什么元素划算 
        }
        //f(1,len,io){
        //  cout << dp[io] << ' ';
        //}cout << endl;//调试 
    }
    cout << len;
    return 0;
}
/*
样例： 
a:  3 2 1 4 5
map:3 2 1 4 5
b:  1 2 3 4 5
dp: 3 -> 2 -> 1 -> 1,4 -> 1,4,5
len:1 -> 1 -> 1 ->  2  ->   3
*/

by qujunhao @ 2024-10-06 16:02:05

@XYstarabyss 已关注，谢谢