题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=25839
思路：第一小问可以很快求出了，两个字符串的长度-LCS，然后第二问就要记忆化搜索了，dp[i][j][l]表示A串的前i个和B串的前j个组合，长度为l的组合数。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 33
#define FILL(a,b) memset(a,b,sizeof(a))
typedef long long ll; int n,len,len1,len2,dp1[MAXN][MAXN];
ll dp2[MAXN][MAXN][MAXN*]; char str1[MAXN],str2[MAXN];
int LCS()
{
FILL(dp1,);
for(int i=;i<=len1;i++){
for(int j=;j<=len2;j++){
if(str1[i-]==str2[j-])dp1[i][j]=dp1[i-][j-]+;
else dp1[i][j]=max(dp1[i-][j],dp1[i][j-]);
}
}
return dp1[len1][len2];
} ll dfs(int l1,int l2,int l)
{
if(dp2[l1][l2][l]!=-)return dp2[l1][l2][l];
else if(l==len)return l1==len1&&l2==len2;
else if(l1==len1)return dp2[l1][l2][l]=dfs(l1,l2+,l+);
else if(l2==len2)return dp2[l1][l2][l]=dfs(l1+,l2,l+);
else if(str1[l1]==str2[l2])return dp2[l1][l2][l]=dfs(l1+,l2+,l+);
return dp2[l1][l2][l]=dfs(l1+,l2,l+)+dfs(l1,l2+,l+);
} int main()
{
int _case=;
scanf("%d",&n);
while(n--){
scanf("%s%s",str1,str2);
len1=strlen(str1),len2=strlen(str2);
len=len1+len2-LCS();
FILL(dp2,-);
printf("Case %d: %d %lld\n",_case++,len,dfs(,,));
}
return ;
}