題目描述

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

輸入格式

第一行是一個數?n。

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

輸出格式

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

輸入輸出樣例

輸入 #1

5 
3 2 1 4 5
1 2 3 4 5

輸出 #1

3

說明/提示

• 對于 50%?的數據， n≤10^3；
• 對于?100%?的數據，n≤10^5；

解題思路

最開始基本解法是二維數組O(n^2)解法顯然過不了，這里需要把題目轉換成求遞增子序列，遞增子序列需要一個貪心的優化

#include<stdio.h>
int n, a[100001], b[100001], c[100001], t, f[100001];
int main()
{int i;scanf("%d", &n);for (i = 1; i <= n; i++){scanf("%d", &a[i]);c[a[i]] = i;f[i] = 1e9;}for (i = 1; i <= n; i++){scanf("%d", &t);b[i] = c[t];}int len = 1; f[1] = b[1];for (i = 2; i <= n; i++){if (b[i] > f[len])f[++len] = b[i];else{int l = 0, mid, r = len, g;while (l <= r){mid = (l + r) / 2;if (f[mid] >= b[i]){g = i;r = mid - 1;}elsel = mid + 1;}if (f[g] > b[i])f[g] = b[i];}}printf("%d", len);return 0;
}