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

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

$$传送门啦$$


题目描述

给出\(1-n\)的两个排列\(P1\)和\(P2\),求它们的最长公共子序列。


输入输出格式

输入格式:

第一行是一个数\(n\),

接下来两行,每行为\(n\)个数,为自然数\(1-n\)的一个排列。


输出格式:

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


输入输出样例

输入样例#1:

5

3 2 1 4 5

1 2 3 4 5

输出样例#1:

3


说明

【数据规模】

对于\(50%\)的数据,\(n≤1000\)

对于\(100%\)的数据,\(n≤100000\)

思路

一看到是一道模板题就觉得不会很难,但还是看到数据时瞬间觉得**,只会五十分的我......所以就发五十分代码吧,什么时候我会了\(n log n\)的做法再来更

50分代码

#include<bits/stdc++.h>
using namespace std; int a[101001],b[101001];
int f[10000][10001];
int 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++) {
f[i][j]=max(f[i-1][j],f[i][j-1]);
if(a[i]==b[j]) {
f[i][j]=max(f[i][j],f[i-1][j-1]+1);
}
}
}
cout<<f[n][n]<<'\n';
return 0;
}
上一篇:最长公共子序列问题(LCS) 洛谷 P1439


下一篇:bzoj2243 染色