萌新想求助,如何实现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;
}
}