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

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

题目描述

给出1, 2, …, n的两个排列P1​和P2​，求它们的最长公共子序列。

输入格式

第一行是一个数n。
接下来两行，每行为n个数，为自然数1, 2, …, n的一个排列。

输出格式

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

输入输出样例

输入#1	输出#1
5 3 2 1 4 5 1 2 3 4 5	3

说明/提示

• 对于50%的数据，n≤103；
• 对于100%的数据，n≤105。

思路：
朴素dp

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 3e3+10;
int n;
int a[N], b[N];
int dp[N][N]; int main() 
{cin >> n;for (int i = 1; i <= n; ++i) cin >> a[i];for (int i = 1; i <= n; ++i) cin >> b[i];for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {if (a[i] == b[j]) {dp[i][j] = dp[i-1][j-1] + 1;} else {dp[i][j] = max(dp[i-1][j], dp[i][j-1]);}}}cout << dp[n][n] << endl;return 0;
}

思路：

排列优化

代码：