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

题目描述

给出 $P_1P1 和 P_2P2 ，求它们的最长公共子序列。$

输入格式

第一行是一个数

接下来两行，每行为

输出格式

一个数，即最长公共子序列的长度。

输入输出样例

输入 #1

5 
3 2 1 4 5
1 2 3 4 5

输出 #1

说明/提示

对于 $50\%50% 的数据， n le 10^3n≤103；$
对于 $100\%100% 的数据， n le 10^5n≤105。$

 1 //Luogu p1439
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 #include <cmath>
 7 #include <string>
 8 using namespace std;
 9 
10 const int N = 1e5+10;
11 
12 int n;
13 int a1[N], a2[N];
14 int belong[N];
15 int f[N], b[N], len;
16 
17 int main(){
18     scanf("%d", &n);
19     for(int i = 1; i <= n; i++) {
20         scanf("%d", &a1[i]);
21         belong[a1[i]] = i;
22     }
23     for(int i = 1; i <= n; i++) scanf("%d", &a2[i]);
24     for(int i = 1; i <= n; i++){
25         if(belong[a2[i]] > b[len]){
26             b[++len] = belong[a2[i]];
27             continue;
28         }else{
29             int k = lower_bound(b+1, b+len+1, belong[a2[i]]) - b;
30             b[k] = belong[a2[i]];
31         }
32     }
33     printf("%d
", len);
34 
35     return 0;
36 }
37 /*
38 //50分做法
39 #include <iostream>
40 #include <cstdio>
41 #include <cstring>
42 #include <algorithm>
43 #include <cmath>
44 #include <string>
45 using namespace std;
46 
47 int n;
48 int dp[1001][1001];
49 int a[1001], b[1001];
50 
51 int main(){
52     scanf("%d", &n);
53     for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
54     for(int i = 1; i <= n; i++) scanf("%d", &b[i]);
55     for(int i = 1; i <= n; i++)
56         for(int j = 1; j <= n; j++){
57             if(a[i] == b[j]){
58                 dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1);
59             }else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
60         }
61     printf("%d
", dp[n][n]);
62 
63     return 0;
64 }
65 */