当前位置 : 主页 > 编程语言 > c++ >

c++最长公共子序列

来源:互联网 收集:自由互联 发布时间:2021-06-23
最长公共子序列 Description Input 第一行:序列A的长度 第二行:给出序列A 第三行:序列B的长度 第四行:给出序列B 长度=1000 Output 只有一行:表示最长的公共子序列的长度 Sample Input 61

最长公共子序列

Description

Input

第一行:序列A的长度 第二行:给出序列A 第三行:序列B的长度 第四行:给出序列B

长度<=1000

Output

只有一行:表示最长的公共子序列的长度

Sample Input

6
1 6 2 5 4 7
7
0 1 2 5 5 2 7

Sample Output

4

Source

#include <bits/stdc++.h>
using namespace std;
int f[1001][1001];
int n, m, a[1001], b[1001];
int main()
{
    cin >> n;
    for(int i = 1;i <= n;i ++) {
        scanf("%d",&a[i]);
    }
    cin >> m;
    for(int i = 1;i <= m;i ++) {
        scanf("%d",&b[i]);
    }
    f[0][0] = 0;
    f[0][1] = 0;
    f[1][0] = 0;
    for(int i = 1;i <= n;i ++) {
        for(int j = 1;j <= m;j ++) {
            if(a[i] == b[j]) {
                f[i][j] = f[i - 1][j - 1] + 1;
            }
            else {
                f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            }
        }
    }
    cout << f[n][m] << endl;
    return 0; 
}
/**************************************************************
    Problem: 1602
    User: LJA001162
    Language: C++
    Result: 正确
    Time:4 ms
    Memory:5460 kb
****************************************************************/
网友评论