萌新求助!关于lcs及它的回溯
  • 板块灌水区
  • 楼主xixi_bang
  • 当前回复1
  • 已保存回复1
  • 发布时间2020/5/5 19:36
  • 上次更新2023/11/7 03:04:58
查看原帖
萌新求助!关于lcs及它的回溯
322896
xixi_bang楼主2020/5/5 19:36

萌新想求助,如何实现lcs路径的回溯?(也就是有哪几位是被选择最终成为lcs的一部分的?)

#include<iostream>
#include<stdio.h>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;
struct pix{
    int x=0,y=0;
};
queue<int> qa;
queue<int> qb;
int dp[105][105];
pix pre[105][105];
int score[5][5]=
{{5,-1,-2,-1,-3},
{-1,5,-3,-2,-4},
{-2,-3,5,-2,-2},
{-1,-2,-2,5,-1},
{-3,-4,-2,-1,0}};
int main(){
    int n,m;
    char a[105],b[105];//对于printf来说不能输入string类型的变量,string为c++类型
    scanf("%d",&n);//输出可以通过string.c_str()实现
    scanf("%s",&a);
    scanf("%d",&m);
    scanf("%s",&b);//第i、j位进行配对
    //求最长公共子序列
    for(int i=0;i<n;i++) dp[i][0]=0;
    for(int i=0;i<m;i++) dp[0][i]=0;

    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
        if(a[i-1]==b[j-1]){
            if(dp[i-1][j-1]+1>dp[i][j]){
               dp[i][j]=dp[i-1][j-1]+1;
               pix t;
               t.x=i-1;
               t.y=j-1;
               pre[i][j]=t;
            }
        }
        else
            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
      //  printf("dp[%d][%d]=%d\n",i,j,dp[i][j]);
    }
    while(pre[n][m].x!=0&&pre[n][m].y!=0){
        printf("%d,%d\n",n,m);
        n=pre[n][m].x;
        m=pre[n][m].y;
    }

}
2020/5/5 19:36
加载中...