aaaaaaaawsl @ 2021-07-17 15:25:42
#include<iostream>
#include<cstdio>
using namespace std;
int a[100001],b[100001],map[100001],f[100001];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++){scanf("%d",&a[i]);map[a[i]]=i;}
for(int i=1;i<=n;i++){scanf("%d",&b[i]);f[i]=0x7fffffff;}
int len=0;
f[0]=0;
for(int i=1;i<=n;i++)
{
int l=0,r=len,mid;
if(map[b[i]]>f[len])f[++len]=map[b[i]];
else
{
while(l<r)
{
mid=(l+r)/2;
if(f[mid]>map[b[i]])r=mid;
else l=mid+1;
}
f[l]=min(map[b[i]],f[l]);
}
}
cout<<len;
return 0
}
看不懂第三个for循环,题解第一篇,主要是len,map,f的作用,求dl解答(我好菜啊
PS:其实题解区哪位dl没解释,我l,r也不懂
PPS:当然可能是我眼瞎,dbq
by ahawzlc @ 2021-07-17 15:50:11
这个我们今天zzy老师也讲了。
整个代码是对LCS的
花姐姐是这么解释上述转化的。
最长公共子序列是按位向后比对的,所以a序列每个元素在b序列中的位置如果递增,就说明b中的这个数在a中的这个数整体位置偏后
len为f数组的有效位置,f就是dp数组,表示当前所记录的最长上升子序列末尾元素,这个是用来进行二分LIS优化的基础。
具体二分过程还是去看花姐姐的注释吧,讲得很明白。
(如果我有哪个地方理解错了还请指正)