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