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,sz2;
int dp;
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>sz1;
}
for(int i=1;i<=n;i++){
cin>>sz2;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
dp=max(dp,dp); //不同，认定为从缺少这两种元素的前一种情况而来
if(sz1==sz2)dp=dp+1; //相同长度加一
}
}
cout<<dp;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]