題目描述
給出 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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/189125.html
標籤：其他
上一篇：微信小程式筆記（1）