7-10 最长公共子序列

目录

题目描述

输入格式:

输出格式:

输入样例:

输出样例:

解题思路：

 详细代码：

---

题目描述

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

n 在 5~1000 之间。

输入格式:

第一行是一个数 n

接下来两行，每行为 n 个数，为自然数 1~n 的一个排列（1~n 的排列每行的数据都是 1~n 之间的数，但顺序可能不同，比如 1~5 的排列可以是：1 2 3 4 5，也可以是 2 5 4 3 1）。

输出格式:

一个整数，即最长公共子序列的长度。
数据范围

对于 25% 的数据 n≤10

对于 50% 的数据 n≤500

对于 75% 的数据 n≤800
对于 100% 的数据 n≤1000

输入样例:

5 
3 2 1 4 5
1 2 3 4 5

输出样例:

3

解题思路：

本题为线性动态规划

存在两种情况

1、如果当前匹配的元素相等，则长度加一

2、如果不相等，两个元素必定有一个可以去除

详细代码：

#include <iostream>
using namespace std;
const int N=1010;
int n,m;
int sz1[N],sz2[N];
int dp[N][N];
int main()
{int n;cin>>n;for(int i=1;i<=n;i++){cin>>sz1[i];}for(int i=1;i<=n;i++){cin>>sz2[i];}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dp[i][j]=max(dp[i-1][j],dp[i][j-1]);    //不同，认定为从缺少这两种元素的前一种情况而来if(sz1[i]==sz2[j])dp[i][j]=dp[i-1][j-1]+1;	//相同长度加一}}cout<<dp[n][n];
}