题意：

每组测试数据有两个DNA，目标串为能保持两个给出的DNA的相对序列且为最小长度的串，并且要输出有多少种构造方法。

思路：

对于求最小串的长度，就很简单了，把LCS的思想直接移植过来就行了：

1. b1[i] == b2[j]  d1[i, j] = d1[i-1, j-1];

2. b1[i] != b2[j]  d1[i, j] = min(d1[i-1, j], d1[i, j-1]) + 1;

对于求有多少种组合方法，定义d2[i, j]表示两个串的前i, j个有多少个组合方法。

1. b1[i] == b2[j]  显然b1[i] b2[j]在最后的摆放次序已经无关了，d2[i, j] = d2[i-1, j-1];

2. b1[i] != b2[j]  此时就要详细讨论了d1[i, j-1]与d1[i-1, j]的大小关系，关系着b1[i], b2[j]在最后的摆放次序。

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int MAXN = 50;int d1[MAXN][MAXN], d2[MAXN][MAXN];char b1[MAXN], b2[MAXN];int main(){    int cases, count = 0;    scanf("%d%*c", &cases);    while (cases--)    {        gets(b1 + 1);        gets(b2 + 1);                for (int i = 0; i < MAXN; ++i)            d1[0][i] = d1[i][0] = i,            d2[0][i] = d2[i][0] = 1;        int len1 = strlen(b1 + 1);        int len2 = strlen(b2 + 1);        for (int i = 1; i <= len1; ++i)            for (int j = 1; j <= len2; ++j)                if (b1[i] == b2[j])                {                    d1[i][j] = d1[i-1][j-1] + 1;                    d2[i][j] = d2[i-1][j-1];                }                else                {                    d1[i][j] = min(d1[i-1][j], d1[i][j-1]) + 1;                    if (d1[i-1][j] < d1[i][j-1])                        d2[i][j] = d2[i-1][j];                    else if (d1[i-1][j] > d1[i][j-1])                        d2[i][j] = d2[i][j-1];                    else                        d2[i][j] = d2[i-1][j] + d2[i][j-1];                }        printf("Case #%d: %d %d\n", ++count, d1[len1][len2], d2[len1][len2]);    }    return 0;}