本文共 1314 字，大约阅读时间需要 4 分钟。

Common Subsequence

时间限制: 1 Sec  内存限制: 128 MB

题目描述

给定序列的子序列是将给定的序列的一些元素（可能没有）省去。给定一个序列X = <x1, x2, ..., xm>另一个序列Z = <z1, z2, ..., zk>是X的子序列存在一个X的指数的严格递增的序列<i1, i2, ..., ik>，对于所有的j = 1,2,...,k, xij = zj。例如，Z = <a, b, f, c>，是X = <a, b, c, f, b, c>的子序列，其索引序列<1, 2, 4, 6>。给定两个序列X和Y，问题是求出X和Y的最大公子序列的长度。

程序输入来自一个文本文件。文件中的每个数据集包含两个字符串，表示给定的序列。这些序列由任意数量的空格分隔。输入数据是正确的。对于每一组数据，每行打印最长度公共子序列的长度。

输入

输出

样例输入

abcfbc abfcabprogramming contest abcd mnp

样例输出

420

   徐不可说：给定两个序列 X=<x1, x2, ..., xm>, Y<y1, y2, ..., yn>，求X和Y长度最长的公共子序列。(子序列中的字符不要求连续)这道题被称为最长公共子序问题，可以用动态规划解决。定义c[i, j]表示Xi和Yj的LCS的长度，可得如下公式：

以下为伪算法：

//int n,m;char s[max_n],t[max_m];int dp[max_n+1][max_m+1];   //dp数组void solve(){    for(int i=0;i

显而易见，这是一种记录结果再利用的“动态规划”方法。

本题的ac代码如下：

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int N = 1000;char a[N],b[N];int dp[N][N];int main() {    while(scanf("%s%s",&a,&b)!=EOF) {        memset(dp,0,sizeof(dp));        int lena=strlen(a);        int lenb=strlen(b);        for(int i=1; i<=lena; i++) {            for(int j=1; j<=lenb; j++) {                if(a[i-1]==b[j-1])                    dp[i][j]=dp[i-1][j-1]+1;                else                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);            }        }        printf("%d\n",dp[lena][lenb]);    }    return 0;}
      
     
    
   

转载地址：http://patgn.baihongyu.com/