UVA 10723--Cyborg Genes+最长公共子序列变形

题目链接：点击进入
首先对于长度最短的情况是很容易确定的，只需要用两个字符串的长度和减去他们的最长公共子序列长度。然后比较麻烦的就是合乎要求的字符串的个数，其实我们也可以用类似于最长公共子序列的dp来求。
设dp[i][j]表示str1的前i个字符和str2的前j个字符所得到的满足要求的字符串，则如果str[i]==str[j]，则dp[i][j]+=dp[i-1][j-1]; 否则就要根据i，j这两个位置上的最长公共子序列长度进行讨论，具体见代码。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn=40;

int dp1[maxn][maxn];
long long dp2[maxn][maxn];
char str1[maxn],str2[maxn];

int main()
{
     // freopen("in.txt","r",stdin);
       int t,Case=0;
       scanf("%d%*c",&t);
       while(t--)
       {
           gets(str1+1);
           gets(str2+1);

            int len1=strlen(str1+1);
            int len2=strlen(str2+1);

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

            for(int i=0;i<=len1;i++)
                dp2[i][0]=1;
            for(int i=0;i<=len2;i++)
               dp2[0][i]=1;

            for(int i=1;i<=len1;i++)
               for(int j=1;j<=len2;j++)
               {
                     if(str1[i]==str2[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][j]==dp1[i-1][j]) ///这两种情况不是对立的
                             dp2[i][j]+=dp2[i-1][j];
                          if(dp1[i][j]==dp1[i][j-1])
                             dp2[i][j]+=dp2[i][j-1];
                     }
               }

           printf("Case #%d: %d %lld\n",++Case,len1+len2-dp1[len1][len2],dp2[len1][len2]);
       }
   return 0;
}