P1439【模板】最长公共子序列实际上这题不能算dp，应该是贪心。先区分两个概念：LIS：LongestIncreasingSubsequence，最长递增子序列LCS：LongestCommonSubsequence，最长公共子序列将b数组中的元素映射为其在a数组中的位置，问题就从LCS变成了LIS。在求解LIS时，开一个单

首先考虑动态规划，a[i]==b[j]，f[i][j]=f[i-1][j-1]+1,否则f[i][j]=max(f[i-1][j],f[i][j-1]);然后看了一眼数据范围，被卡的实施的，然后考虑优化，看到题目是一个排列于是不要考虑重复的问题，于是只在b里看，如果b[i]在a中的位置，小于我们维护的最长的就不行，否则的话直接加入我们维护的最长

link【模板】最长公共子序列题目描述给出$1,2,\ldots,n$的两个排列$P_1$和$P_2$，求它们的最长公共子序列。输入格式第一行是一个数$n$。接下来两行，每行为$n$个数，为自然数$1,2,\ldots,n$的一个排列。输出格式一个数，即最长公共子序列的长度。样例#1样例输入#1

原题链接：https://www.luogu.com.cn/problem/P1439题意解读：求最长公共子序列的长度。解题思路：1、O(n^2)的方法：动态规划设两个排列为a，b设dp[i][j]表示a[1~i]与b[1~j]的最长公共子序列长度根据公共子序列结尾是否包含a[i]、b[j]是否相等分情况讨论：如果a[i]==b[j]  则结尾

题面：回顾下最长公共子序列：if(a[i]!=b[j])dp[i][j]=max(dp[i-1][j],dp[i][j-1]);elsedp[i][j]=dp[i-1][j-1]+1;复杂度为O(n^2)但是这题不行，数据卡到了1e5，所以应该再次观察：注意到是两个全排列，那么利用map，把第一个序列当作基准列，做等效替换：把原来的值替换成1，2，3...

P1439【模板】最长公共子序列题意简述给出\(1,2,…,n\)的两个排列\(P_1\)和\(P_2\)，求它们的最长公共子序列。范围限制：\(n\le10^5\)。样例53214512345输出：3。思路简述这道题看似是最长公共子序列，但是发现如果用\(O(n^2)\)的复杂度实现\(LCS\)就会时

首先找最大公共子序列，可以轻松想到$O(n^2)$的dp转移式子，$f_{i,j}=max\begin{cases}f_{i-1,j}&i>0\f_{i,j-1}&j>0\f_{i-1,j-1}+1&i>0,j>0,A_i=A_j\end{cases}$但是我们发现最后$n\le10^5$所以$n^2$的复杂度不够优，这个时候再看题目，发现A，B都是 1~n的排列，由此可知A，B

轻敌了啊...题目一共只有几句话但我却忽略了一个重大信息...总之我显示写出了时空复杂度都是n^2级别的朴素递推算法，这没什么，基本功而已，然后50分我试了试滚动数组，把空间复杂度降到了n级别，但没什么用，解决了MLE但仍然TLE。后来我想到记搜应该能算的更快，毕竟有些用不到的点用搜索就

前置知识：\(LIS\):即最长上升子序列(\(Longest\)\(Increasing\)\(Subsequence\))LuoguB3637最长上升子序列这是一个简单的动规板子题。给出一个由\(n(n\le5000)\)个不超过\(10^6\)的正整数(\(x_1,x_2,\cdots,x_n\))组成的序列。请输出这个序列的最长上升子