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
    输入样例:

1. 5
2. 3 2 1 4 5
3. 1 2 3 4 5

复制代码

   输出样例:

1. 3

复制代码

   解题思绪：

  本题为线性动态规划
  存在两种环境
  1、如果当前匹配的元素相称，则长度加一
  2、如果不相称，两个元素必定有一个可以去除
    详细代码：

1. #include <iostream>
2. using namespace std;
3. const int N=1010;
4. int n,m;
5. int sz1[N],sz2[N];
6. int dp[N][N];
7. int main()
8. {
9.         int n;
10.         cin>>n;
11.         for(int i=1;i<=n;i++){
12.                 cin>>sz1[i];
13.         }
14.         for(int i=1;i<=n;i++){
15.                 cin>>sz2[i];
16.         }
17.         for(int i=1;i<=n;i++)
18.         {
19.                 for(int j=1;j<=n;j++)
20.                 {
21.                         dp[i][j]=max(dp[i-1][j],dp[i][j-1]);    //不同，认定为从缺少这两种元素的前一种情况而来
22.                         if(sz1[i]==sz2[j])dp[i][j]=dp[i-1][j-1]+1;        //相同长度加一
23.                 }
24.         }
25.         cout<<dp[n][n];
26. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。