问题标题: 酷町堂：5088 最长公共子序列 2

Question

0

已解决

王子健

初级天翼

5088 最长公共子序列 2 经验值：0

题目描述 Description

给出两个字符串A B，求A与B的最长公共子序列（子序列不要求是连续的）。比如两个串为：abcicba和abdkscab。ab是两个串的子序列，abc也是，abca也是，其中abca是这两个字符串最长的子序列。

输入描述 Input Description

第1行：字符串A
第2行：字符串B
(A,B的长度 <= 1000)

输出描述 Output Description

输出最长的子序列，如果有多个，输出在B中最后一个出现的公共子序列

样例输入 Sample Input

abcicba abdkscab

样例输出 Sample Output

abcb

老师说这题好简单，我还是10分.....大佬帮看下

#include <iostream>
#include <cstdio>
using namespace std;
string a, b; 
int f[1010][1010], g[1010][1010], la, lb;
void dfs(int i, int j) {
    if (g[i][j] == 1) {
        dfs(i-1, j-1);
        cout << b[j];
    } else if (g[i][j] == 2) {
        dfs(i-1, j);
    } else if (g[i][j] == 3) {
        dfs(i, j-1);
    }
}
int main() {
    cin >> a >> b;
    la = a.size();
    lb = b.size();
    a = " " + a;
    b = " " + b;
    for (int i=1; i<=la; i++) {
        for (int j=1; j<=lb; j++) {
            if (a[i] == b[j]) {
                f[i][j] = f[i-1][j-1] + 1;
                g[i][j] = 1;
            } else if (f[i-1][j] > f[i][j-1]) {
                f[i][j] = f[i-1][j];
                g[i][j] = 2;
            } else if (f[i-1][j] <= f[i][j-1]) {
                f[i][j] = f[i][j-1];
                g[i][j] = 3;
            }
        }
    }
    dfs(la, lb);
    return 0;
}

Answer 1

已采纳

赵逸凡

初级启示者

现在你学到了dp吗？

>和<=是什么鬼？是找公共子序列，判断是否等于

Answer 2

王子健

初级天翼

快来人吧

Answer 3

曹砚青

中级光能

没办法，兄弟，我只有80。

#include<iostream>
using namespace std;
string a,b;
int f[1005][1005],g[1005][1005];
void print(int x,int y){
    if(x==0||y==0)
        return ;
    if(g[x][y]==1){
        print(x-1,y-1);
        cout<<b[y];
    }
    else if(g[x][y]==2)
        print(x-1,y);
    else
        print(x,y-1);
}
int main(){
    getline(cin,a);
    getline(cin,b);
    int m=a.length(),n=b.length();
    a=" "+a;
    b=" "+b;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            if(a[i]==b[j]){
                f[i][j]=f[i-1][j-1]+1;
                g[i][j]=1;
            }
            else if(f[i-1][j]>=f[i][j-1]){
                f[i][j]=f[i-1][j];
                g[i][j]=2;
            }
            else{
                f[i][j]=f[i][j-1];
                g[i][j]=3;
            }
    print(m,n);
    return 0;
}

问题标题: 酷町堂：5088 最长公共子序列 2

3 个回答: