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

思路讲解

https://www.luogu.com.cn/article/63o898db

如果说一个序列是1，2，3，4，5，……，N，还有一个序列无序，那么其实就选一个LIS就行。

那么现在前面这个序列不是有序的，但前面这个序列的标号是有序的，这个时候怎么搞？其实我们就定义新的顺序为A[1]<A[2]<A[3]……<A[N]，就行了

scanf("%lld",&N);
FOR(i,1,N) {scanf("%lld",&A[i]);posA[A[i]]=i;}
FOR(i,1,N) {scanf("%lld",&B[i]);}
vector<ll> dp;
FOR(i,1,N){
	if(dp.empty()) dp.pb(posA[B[i]]);
	else{
		vector<ll>::iterator it=lower_bound(all(dp),posA[B[i]]);
		if(it==dp.end()) dp.pb(posA[B[i]]);
		else dp[it-dp.begin()]=posA[B[i]];
	}
}
printf("%d\n",SZ(dp));

AC代码

https://www.luogu.com.cn/record/219257679

源代码

// Problem: P1439 【模板】最长公共子序列
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1439
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
// #define getFro(vec) (vec.empty()?0:vec.front())
// #define getBac(vec) (vec.empty()?0:vec.back())
#define debug(var) cerr << #var <<":"<<var<<"\n";
// #define DEBUG(variable) do { std::cerr << #variable << ":"; for (const auto& elem : \
// variable) { std::cerr << elem << " ";}std::cerr << "\n";} while (0)
// #define uniVec(var) do {  sort(var.begin(),var.end());var.resize(unique(var.begin(), \
// var.end())-var.begin());} while (0)
// #define debugN(var,N) do{ std::cerr<<#var<<":"; FOR(i,1,N){ std::cerr<<var[i]<<" "; } \ 
// std::cerr<<"\n"; }while(0)
// #define debugMap(variable) do { std::cerr << #variable << ":\n"; for (const auto \
// & pair : variable) \
// { std::cerr << "  " << pair.first << " => " << pair.second << "\n"; } \
// std::cerr << std::endl; } while (0)
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
// #define vecMxx(vec,x) (vec.end()-lower_bound(all(vec),x))	// vec中大于x的数有几个

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e5)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN],B[MAXN];
/*

*/
ll posA[MAXN];
inline void solve(){
	scanf("%lld",&N);
	FOR(i,1,N) {scanf("%lld",&A[i]);posA[A[i]]=i;}
	FOR(i,1,N) {scanf("%lld",&B[i]);}
	vector<ll> dp;
	FOR(i,1,N){
		if(dp.empty()) dp.pb(posA[B[i]]);
		else{
			vector<ll>::iterator it=lower_bound(all(dp),posA[B[i]]);
			if(it==dp.end()) dp.pb(posA[B[i]]);
			else dp[it-dp.begin()]=posA[B[i]];
		}
	}
	printf("%d\n",SZ(dp));
}

int main()
{
	// ios::sync_with_stdio(false);
	// cin.tie(0);cout.tie(0);
	
	// scanf("%lld",&lT);
	// while(lT--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://www.luogu.com.cn/record/219257679
*/

心路历程（WA，TLE，MLE……）