51Nod-1006【LCS】+【输出路径】模板题

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题目链接：https://vjudge.net/contest/225715#problem/B

转载于>>>

题目大意：

给出两个序列，要求输出它们的最长公共子序列。

解题思路：

最长公共子序列模板题～

我们用dp[i][j]表示到a串第i个字符, b串第j个字符的最大匹配字符数，那么状态转移方程为：

dp[i][j]=dp[i-][j-]+ a[i]==b[j]dp[i][j]=max(dp[i][j-], dp[i-][j]) a[i]!=b[j]

我们可以这样理解：dp[i][j]表示第a串前i个字符与b串前j个字符的最大匹配数，dp[i-1][j-1]表示a字符前i-1个字符与b串前j-1个字符的最大匹配数

如果a[i]=b[j]，那么很明显dp[i][j]=dp[i-1][j-1]+1；

若a[i]!=b[j]，我们假设a, b的最大匹配串为c，显然a[i], b[j]不能同时作为c的最后一个字符，那么最优匹配情况即为a[i]为c的最后一个字符或者b[j]为c的最后一个字符(这点不大好理解),即

dp[i][j]=dp[i][j-1] a[i]是c的最后一个字符即匹配的末尾字符

dp[i][j]=dp[i-1][j] b[j]是c的最后一个字符即匹配的末尾字符（其实当a[i], b[j]都不是c的最后一个字符时即a[i], b[j]都不匹配时dp[i][j]=dp[i-1][j-1]）

又dp要取最大值，即dp[i][j]=max(dp[i][j-1], dp[i-1][j])

题目还要求要输出一个最优匹配串，这个我们用vis[][]数组在dp过程中记录一下路径就好啦～

非递归输出路径

#include <bits/stdc++.h>
using namespace std;
#define MAXN 1010
int dp[MAXN][MAXN];
int vis[MAXN][MAXN];
string stra, strb;
char output[MAXN]; int cur = ;void getlcs(int i, int j)
{
while (i>&&j>) //逆推取出vis中保存的路径
{
if (vis[i][j]==) {
output[cur++] = stra[i - ];
i--; j--;
}
else if (vis[i][j] == ) {
j--;
}
else {
i--;
}
}
}int main()
{
cin >> stra >> strb;
int lena = stra.length();
int lenb = strb.length();
for (int i = ; i <= lena; i++){
for (int j = ; j <= lenb; j++) {
if (stra[i - ] == strb[j - ]) {
dp[i][j] = dp[i - ][j - ] + ;
vis[i][j] = ; //vis数组标记路径
}
else {
if (dp[i - ][j] < dp[i][j - ]) {
dp[i][j] = dp[i][j - ];
vis[i][j] = ;
}
else {
dp[i][j] = dp[i - ][j];
vis[i][j] = ;
}
}
}
}
getlcs(lena, lenb);
for (int i = cur - ; i >= ; i--) //逆向输出
printf("%c", output[i]);
cout << endl;
return ;
}

递归输出路径

#include <bits/stdc++.h>
using namespace std;
#define MAXN 1010
int dp[MAXN][MAXN];
int vis[MAXN][MAXN];
string stra, strb;void getlcs(int i, int j) { //**输出路径
if (!i || !j) { //因为i-1要>=0
return;
}
if (vis[i][j] == ) {
getlcs(i - , j - );
printf("%c", stra[i - ]);
}
else if (vis[i][j] == ) {
getlcs(i, j - );
}
else {
getlcs(i - , j);
}
}int main()
{
cin >> stra >> strb;
int lena = stra.length();
int lenb = strb.length();
for (int i = ; i <= lena; i++){
for (int j = ; j <= lenb; j++) {
if (stra[i - ] == strb[j - ]) {
dp[i][j] = dp[i - ][j - ] + ;
vis[i][j] = ; //vis数组标记路径
}
else {
if (dp[i - ][j] < dp[i][j - ]) {
dp[i][j] = dp[i][j - ];
vis[i][j] = ;
}
else {
dp[i][j] = dp[i - ][j];
vis[i][j] = ;
}
}
}
}
getlcs(lena, lenb);
cout << endl;
return ;
}