【Uva 10723】Cyborg Genes

【Link】:

【Description】



给你两个串s1,s2;

让你生成一个串S;

使得s1和s2都是S的子列;

要求S最短;

求S的不同方案个数;

【Solution】



设两个串的长度分别为n1和n2;

则答案为n1+n2-两个串的最长公共子序列

不同的串则可以在求最长公共子序列的时候顺便求出;

设dp2[i][j],表示第一个字符串前i个字符,第二个字符串前j个字符能组成的不同的字符串的个数;

dp1[i][j]是最长公共子序列数组

如果

s1[i]==s2[j],dp2[i][j] = dp2[i-1][j-1];

(表示在dp2[i-1][j-1]所表示的所有字符串的末尾再加上一个s1[i])

s1[i]!=s2[j]:

①dp1[i-1][j]>dp1[i][j-1],则dp2[i][j] = dp2[i-1][j]

(表示在dp[i-1][j]所表示的所有字符串末尾再加上一个s1[i]);

②dp1[i-1][j]< dp1[i][j-1],则dp2[i][j] = dp2[i][j-1];

(同理)

③dp1[i-1][j]==dp1[i][j-1],则dp2[i][j] = dp2[i][j-1]+dp2[i-1][j];

(两个都是最长的,则两个都能加上s1[i]或s2[j]组成符合要求的字符串)

有空串,用gets..



【NumberOf WA】



1



【Reviw】



最长公共子序列的变形题;



【Code】

#include <bits/stdc++.h>

using namespace std;

#define LL long long

const int N = 30;

char s1[N+5],s2[N+5];

LL dp1[N+5][N+5],dp2[N+5][N+5];

int n1,n2;

int main(){

    //freopen("F:\\rush.txt","r",stdin);

    int T;

    scanf("%d",&T);

    getchar();

    for (int ii = 1;ii <= T;ii++){

        gets(s1+1);

        gets(s2+1);

        memset(dp1,0,sizeof dp1),memset(dp2,0,sizeof dp2);

        n1 = strlen(s1+1),n2 = strlen(s2+1);

        for (int i = 0;i <= n1;i++)

            dp2[i][0] = 1;

        for (int i = 1;i <= n2;i++)

            dp2[0][i] = 1;

        for (int i = 1;i <= n1;i++)

            for (int j = 1;j <= n2;j++)

                if (s1[i]==s2[j]){

                    dp1[i][j] = dp1[i-1][j-1]+1;

                    dp2[i][j] = dp2[i-1][j-1];

                }else{

                    dp1[i][j] = max(dp1[i-1][j],dp1[i][j-1]);

                    if (dp1[i-1][j] > dp1[i][j-1])

                        dp2[i][j] = dp2[i-1][j];

                    else

                        if (dp1[i-1][j] < dp1[i][j-1])

                            dp2[i][j] = dp2[i][j-1];

                        else

                            dp2[i][j] = dp2[i-1][j] + dp2[i][j-1];

                }

        printf("Case #%d: %lld %lld\n",ii,(LL) n1+n2-dp1[n1][n2],dp2[n1][n2]);

    }

    return 0;

}