UVA - 10723 Cyborg Genes（LCS 最长公共子序列）

问题

两个由A-Z字母组成的长度不超过30个字符的字符串A，B，找一个最短的串C，使得A，B是它的子序列（不一定连续出现），输出最短的长度和个数

分析

这题求最短长度很简单，就是用两个的长度之和减去LCS的长度：len(A)+len(B)-LCS
LCS的状态转移方程： lcs(i,j)代表A(i)和B(j)这两个子串的最大公共序列长度,num[i][j]是对应的最短字符串的个数
$当A[i]==B[j]时，lcs(i,j)=lcs(i-1,j-1)$
$当A[i]!=B[j]时，lcs(i,j)=max(lcs(i-1,j),lcs(i,j-1))$
$i==0或j==0lcs(i,j)=0$

求有最短长度的串的个数时：
1.可以理解为DP的路径数，如果从某条路走过来，路径数不变，如果两条路都可以走过来，路径数就是它们的和
2.也可以换种方法更加详细理解:

$当A[i]==B[j]时，num(i,j)=num(i-1,j-1)$
//两个字母相等A[i]==B[j]时，这一个字母一定在LCS中,最优解就是num[i-1][j-1]的解后面加一个A[i]，所以个数等于num[i-1][j-1]

$当A[i]!=B[j]时，ifnum(i-1,j)!=num(i,j-1)num(i,j)=max(num(i-1,j),num(i,j-1))elsenum(i,j)=num(i-1,j)+num(i,j-1)$
//两个字母不相等，那么A[i],B[j]最多一个在LCS中，也有可能一个都不在
//lcs[i-1][j]>lcs[i][j-1] B[j]在LCS中，A[i]不在,那么解就是num[i-1][j]的解，后面加上一个A[i]
//lcs[i-1][j]<lcs[i][j-1] A[i]在LCS中，B[j]不在，解是num[i][j-1]的解，后面加上一个B[j]
//特殊情况 lcs[i-1][j]==lcs[i][j-1]，A[i],B[j]都不在LCS中,所以结果是两者之和

$i==0或j==0num(i,j)=1$

bug

这一题的数据有问题，应该不全是字母，里面有空格，用scanf会报错，换成gets就行了

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
const int maxn=35;
int lcs[maxn][maxn],kase=0,T;
long long num[maxn][maxn];
char A[maxn],B[maxn];
int main(void){
    scanf("%d\n",&T);
    while(kase<T){
//        scanf(" %s %s",A+1,B+1);
        gets(A+1);
        gets(B+1);
        int len1=strlen(A+1),len2=strlen(B+1);
        for(int i=0;i<=len1;++i){ lcs[i][0]=0; num[i][0]=1;}
        for(int j=0;j<=len2;++j){ lcs[0][j]=0; num[0][j]=1;}

        for(int i=1;i<=len1;++i){
            for(int j=1;j<=len2;++j){
                //两个字母相等，这一个字母一定在LCS中,最优解就是[i-1][j-1]的解后面加一个A[i]，所以个数等于num[i-1][j-1]
                if(A[i]==B[j]){
                    lcs[i][j]=lcs[i-1][j-1]+1;
                    num[i][j]=num[i-1][j-1];
                }else{  //两个字母不相等，那么A[i],B[j]最多一个在LCS中，也有可能一个都不在
                    if(lcs[i-1][j]>lcs[i][j-1]){//B[j]在LCS中，A[i]不在,那么解就是[i-1][j]的解，后面加上一个A[i]
                        lcs[i][j]=lcs[i-1][j];
                        num[i][j]=num[i-1][j];
                    }else if(lcs[i-1][j]<lcs[i][j-1]){//A[i]在LCS中，B[j]不在，解是[i][j-1]的解，后面加上一个B[j]
                        lcs[i][j]=lcs[i][j-1];
                        num[i][j]=num[i][j-1];  //数量相等
                    }else{  //特殊情况 lcs[i-1][j]==lcs[i][j-1]，A[i],B[j]都不在LCS中,所以结果是两者之和
                        lcs[i][j]=lcs[i][j-1];
                        num[i][j]=num[i][j-1]+num[i-1][j];//在num[i][j-1]对应的解后面加B[j],在num[i-1][j]对应的解后面加B[j]A[i]
                    }
                }
            }
        }
        printf("Case #%d: %d %lld\n",++kase,len1+len2-lcs[len1][len2],num[len1][len2]);
    }
}