前言：
本系列目的是记录日常所刷的题，有的是自己想出来的题，有的是看了大佬题解后想明白的题
题目
P1439 【模板】最长公共子序列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
前提：
两个排列都是1到n的排列，说明元素都是相同的只是顺序不同，
思路：
把LCS转换成LIS
原因：
通过离散化可以得到一个性质。
离散化步骤：
A:3 2 1 4 5
B:1 2 3 4 5
重新把A,B数组中的元素替换掉，使得A数组是其次递增的
标个号:把3标成a,把2标成b，把1标成c.…于是变成:
A: a b c d e
B: c b a d e
结论：最长公共子串的长度不会改变，又因为A数组是递增的，所以说在B数组中递增的子序列就是A的子序列
离散化代码：
for (int i = 1; i <= n; i++){cin >> m;line[m] = i;}整体代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;
int n,m,total;
int ans[N],line[N];//line数组是第一个序列离散化后的数组,ans数组是第二个序列离散化后的数组
int main()
{cin >> n;for (int i = 1; i <= n; i++){cin >> m;line[m] = i;}for (int i = 1; i <= n; i++){cin >> m;int search = line[m];if (search > ans[total])ans[++total] = search; else{ int l = 0, r = total;while (l <= r){int mid = ans[(l + r)>> 2];if (search < mid) r = mid - 1;elsel = mid + 1;}ans[l] = search;}}cout << total;
}
