CJOJ 2044 【一本通】最长公共子序列(动态规划)

时间:2023-03-09 04:47:53
CJOJ 2044 【一本通】最长公共子序列(动态规划)

CJOJ 2044 【一本通】最长公共子序列(动态规划)

Description

一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说,若给定序列X,则另一序列Z是X的子序列是指存在一个严格递增的下标序列 ,使得对于所有j=1,2,…,k有 Xij=Zj 。

例如,序列Z是序列X的子序列,相应的递增下标序列为<2,3,5,7>。

给定两个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列。

最长公共子序列(LCS)问题:给定两个序列X=和Y=,要求找出X和Y的一个最长公共子序列。

Input

输入两行,每行由大写字母构成的长度不超过200的字符串,表示序列X和Y

Output

第一行非负整数N,表示最长公共子串的长度,若不存在公共子序列输出0.

第二行输出最长的公共子序列(若存在多个,输出最先出现的最长公共子序列)

Sample Input

ABCDDAB

BDCABA

Sample Output

4

Http

CJOJ:http://oj.changjun.com.cn/problem/detail/pid/2044

Source

动态规划

解决思路

这道题是一道动态规划的经典题目。

我们定义F[i][j]表示字符串A的前i位和字符串B的前j位能取到的最长公共子序列,那么自然有F[i][0]均为0,F[0][i]也均为0。

首先我们可以确定的是对于任意的F[i][j],均可以从F[i-1][j](即字符串A减去一个字符)和F[i][j-1](即字符串B减去一个字符)得到,所以必有F[i][j]=min(F[i-1][j]+F[i][j-1])。那么如果A[i]==B[j],则说明F[i][j]还可以从F[i-1][j-1]推得。

所以,综上所述,动态转移方程就是

\[F[i][j]=min(F[i-1][j-1],F[i-1][j],F[i][j-1]) (A[i]==B[j])
=min(F[i-1][j],F[i][j-1]) (Other)\]

另外,这道题的加强版在这里。因为数据范围的关系,不能在使用本题这种动态规划 的方法。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
using namespace std; const int maxN=300;
const int inf=2147483647; string A;
string B;
int F[maxN][maxN]; int main()
{
memset(F,0,sizeof(F));
cin>>A>>B;
for (int i=0;i<A.size();i++)
F[i][0]=0;
for (int i=0;i<B.size();i++)
F[0][i]=0;
for (int i=1;i<=A.size();i++)
for (int j=1;j<=B.size();j++)
if (A[i-1]==B[j-1])
{
F[i][j]=max(F[i-1][j-1]+1,max(F[i-1][j],F[i][j-1]));
}
else
F[i][j]=max(F[i-1][j],F[i][j-1]);
cout<<F[A.size()][B.size()]<<endl;
return 0;
}