1737: 【基础】最长公共子序列(LCS)(1)

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：3 解决：3

题目描述

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

输入

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

输出

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

样例输入 复制 

5 
3 2 1 4 5
1 2 3 4 5

样例输出 复制 

3

提示

dp[i][j]: 第1个串的前 i 位，第2个串的前 j 位最长公共子序列的长度。
#include<bits/stdc++.h>

using namespace std;
/*
a[i]==b[j],方程:dp[i-1][j-1]+1
a[i]!=b[j],方程:max(dp[i][j-1],dp[i-1][j])
*/
const int N = 1010; //常量，表示数组大小
int a[N], b[N], dp[N][N];
int n, i, j;
int main() {
    cin >> n;
    for (i = 1; i <= n; i++) cin >> a[i];
    for (i = 1; i <= n; i++) cin >> b[i];
    //递推
    for (i = 1; i <= n; i++) {
        for (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];
    return 0;
}

来源/分类

提交提交记录统计露一手!