洛谷 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;
}