最长公共子序列（lcs）到最长上升子序列（lis）的转化。 把第一个串的元素，转化为第二个串的位置，再倒过来，找最长上升子序列。 别问我为什么，我也不知道。。。。。
简单说明：上面的序列和最长公共子串是等价的。 对于一个满足最长严格递增子序列的序列，该序列必对应一个匹配的子串。 反序是为了在递增子串中，每个字母对应的序列最多只有一个被选出。 反证法可知不存在更大的公共子串，因为如果存在，则求得的最长递增子序列不是最长的，矛盾。
#include<cstdio> #include<iostream> #include<cstring> #include<map> #define ll long long using namespace std;int a[999999],m,n,s[999999],len=1,b[999999],low[99999]; map <int,int> f; int twopoint(int x,int y,int z){ int l=x,r=y; while(l<=r) { int mid=(l+r)>>1; if(low[mid]>=z){ r=mid-1; } else l=mid+1; } return l; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } for(int i=1;i<=m;i++) { scanf("%d",&s[i]); f[s[i]]=i; } for(int i=1;i<=n;i++) b[i]=f[a[i]]; int t=0; while(b[t]==0) t++; low[1]=b[t]; for(int i=2;i<=n;i++) { if(b[i]>low[len]) low[++len]=b[i]; else{ int w=twopoint(1,len,b[i]); //low[lower_bound(low+1,low+len+1,b[i])-low]=b[i]; low[w]=b[i]; } } printf("%d",len); }