最长公共子序列（lcs）到最长上升子序列（lis）的转化。
把第一个串的元素，转化为第二个串的位置，再倒过来，找最长上升子序列。
别问我为什么，我也不知道。。。。。
简单说明：上面的序列和最长公共子串是等价的。
对于一个满足最长严格递增子序列的序列，该序列必对应一个匹配的子串。
反序是为了在递增子串中，每个字母对应的序列最多只有一个被选出。
反证法可知不存在更大的公共子串，因为如果存在，则求得的最长递增子序列不是最长的，矛盾。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50#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);
}