洛谷P1439 【模板】最长公共子序列

这题的思路太妙了

思路

首先我作为一个蒟蒻，只能想到50分的做法，而且由于太好想了几乎是秒出答案。但是100分做法我直接放弃想了。。。因为我也意识到自己(dp)太菜了不可能想出来。但是看到了一篇绝妙的题解，直接把这题秒了。简而言之，首先，答案序列一定是(A)的子序列，由于两个序列都是1~n的，那么我们可以强制将(A)数组变为顺序，然后在(B)数组中对应修改，再求出(B)数组的最长上升子序列。

比如说样例中(A)={3,2,1，4,5}。那么我将(A)强制变为{1,2,3,4,5}，将每个数的数值对应到下标，再将(B)序列转化成下标，求最长上升子序列即可。正确性其实很显然，因为子序列一定在(A)中顺序排列，所以说只要在(B)中对应之后找最长上升子序列即可。即(B)中满足序列(A)顺序的最长子序列。

代码

(O(nlogn))求最长上升子序列板子不解释

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<ctime>
using namespace std;
typedef long long ll;
int n;
int a[100005],b[100005],map[100005],f[100005],len;
int main()
{
	scanf("%d",&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]);
		b[i]=map[b[i]];
	}
	f[0]=0;
	for(int i=1;i<=n;i++){
		if(b[i]>f[len]){
			f[++len]=b[i];
		}
		else{
			int p=upper_bound(f+1,f+1+len,b[i])-f;
			f[p]=b[i];
		}
	}
	printf("%d
",len);
	return 0;
}