【題解】【模板】最長公共子序列（LCS）

題目描述

給出 1,2,…,n 的兩個排列P1和P2，求它們的最長公共子序列。

輸入格式

第一行是一個數 n。

接下來兩行，每行為 n 個數，為自然數1,2,…,n 的一個排列。

輸出格式

一個數，即最長公共子序列的長度。

輸入輸出樣例

輸入
5
3 2 1 4 5
1 2 3 4 5
輸出
3
說明/提示
對於 50% 的資料， n≤10^3
對於 100% 的資料，n≤10^5

思路

對於50%的資料，可以考慮動態規劃，設dp[i][j]表示子序列Ai和Bi的最長公共子序列的長度
當Ai = Bi時，找出Ai-1和Bi-1的最長公共子序列，然後在其尾部加上Ai即可得到A和B的最長公共子序列
當Ai != Bi 時，求解兩個子問題：
1、求Ai-1和Bi的最長公共子序列
2、求Ai和Bi-1的最長公共子序列
然後取1、2中的最大值
即

Ai=Bi -> dp[i][j]= dp[i-1][j-1]+1

Ai!=Bi -> dp[i][j]=max(dp[i][j-1],dp[i-1][j])

DP程式碼

#include<bits/stdc++.h>
using namespace std;
const int N=2010;
int dp[N][N],a[N],b[N],n;
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int i=1;i<=n;i++) scanf("%d",&b[i]);
	for (int i=1;i<=n;i++)
	  for (int j=1;j<=n;j++)
	  {
	  	dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
	  	if (a[i]==b[j])
	  	  dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
	  } 
	  cout<<dp[n][n]<<endl;
	  return 0;
}

由於上面的程式碼用到了雙重回圈，時間複雜度為O（n^2)，對於100%的資料是不行的，於是一位洛谷大佬站了出來，說了下面這一段話：

因為兩個序列都是 1~n的全排列，那麼兩個序列元素互異且相同，也就是說只是位置不同罷了，那麼我們通過一個 map陣列將 A序列的數位在 B序列中的位置表示出來——

因為最長公共子序列是按位元向後比對的，所以a序列每個元素在b序列中的位置如果遞增，就說明b中的這個數在a中的這個數整體位置偏後，可以考慮納入 LCS——那麼就可以轉變成 nlogn求用來記錄新的位置的map陣列中的 LIS。

巧妙地將LCS（最長公共子序列）轉換成了LIS（最長遞增子序列）

程式碼

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,len,a[N],m[N],b[N],f[N];
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) 
	{
		scanf("%d",&a[i]);
		m[a[i]]=i;
	}
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&b[i]);
		f[i]=99999999;
	}
	f[0]=0;
	for (int i=1;i<=n;i++)
	{
		if (m[b[i]]>f[len]) f[++len]=m[b[i]];
		else
		{
			/*int l=0,r=len;
			while (l<r)
			{
				int mid=(l+r)/2;
				if (f[mid]>m[b[i]]) r=mid;
				else l=mid+1;
			}
			f[l]=min(m[b[i]],f[l]);*/
			int k=lower_bound(f+1,f+1+len,m[b[i]])-f; //這段程式碼相當於上面的一串二分查詢，就是尋找f[]中第一個大於等於m[b[i]]的數的位置
			f[k]=min(m[b[i]],f[k]);
		} 
	}
	cout<<len<<endl;
	return 0;
}