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

樸素版
o(n^2)

  for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
     {
    
     	dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
     	if(a1[i]==a2[j])
     	dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
     	//因為更新，所以++； 
     }

此題n<=1e5 有nlog做法
因為兩個序列都是1~n1 n的全排列，那麼兩個序列元素互异且相同，也就是說只是比特置不同罷了，那麼我們通過一個mp數組將A序列的數字在B序列中的比特置錶示出來——

如果當前b[i[在a序列的比特置 大於當前最長序列的比特置 直接加入
否則 更新 b[i]在a序列的比特置是否優於其他公共子序列

#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <math.h>
#include <string>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <time.h>
#include <set>
#include <list>
#include <iostream>

using namespace std;
//map<string,string>ip;	
//map<string,bool>cy; 

typedef long long ll;
typedef pair<int,int> PII;
const int maxn=1e5+188;
const ll inf=1e10;
ll n,m,k,flag,cnt,sum;
//map<string,string>mp;
int a[100001],b[100001],mp[100001],f[100001];
int main()
{
    
	cin>>n;
	for(int i=1;i<=n;i++){
    scanf("%d",&a[i]);mp[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(mp[b[i]]>f[len])f[++len]=mp[b[i]];
		else 
		{
    
		while(l<r)
		{
    	
		    mid=(l+r)/2;
		    if(f[mid]>mp[b[i]])r=mid;
			else l=mid+1; 
		}
		f[l]=min(mp[b[i]],f[l]);
     	}
    }
    cout<<len;
    return 0;
}