ToB企服应用市场:ToB评测及商务社交产业平台

标题: 7-10 最长公共子序列 [打印本页]

作者: 自由的羽毛 时间: 2024-12-28 20:59
标题: 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

复制代码

输出样例:

复制代码

解题思绪：

  本题为线性动态规划
  存在两种环境
  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];
}

复制代码

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

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)