https://vjudge.net/problem/UVA-10723
题意：
输入两个A~Z组成的字符串，找一个最短的串，使得输入的两个串均是它的子序列，另外还需要统计长度最短的串的个数。
思路：
求两个串的公共子序列。那么最短串就是len1+len2-LCS值。
d[i][j]表示串1取前 i 个字符，串2取前 j 个字符时的LCS。
状态转移方程如下：
如果A[i]=A[j]，d[i][j]=d[i-1][j-1]+1。否则，d[i][j]=max( d[i-1][j] ，d[i][j-1] )。
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std; char s1[], s2[];
int d[][], f[][]; int main()
{
//freopen("D:\\txt.txt", "r", stdin);
int T;
int kase = ;
cin >> T;
getchar();
while (T--)
{
gets(s1);
gets(s2);
int len1 = strlen(s1);
int len2 = strlen(s2);
memset(d, , sizeof(d));
memset(f, , sizeof(f));
for (int i = ; i <= len1; i++)
f[i][] = ;
for (int i = ; i <= len2; i++)
f[][i] = ;
for (int i = ; i <= len1;i++)
for (int j = ; j <= len2; j++)
{
if (s1[i - ] == s2[j - ])
{
d[i][j] = d[i - ][j - ] + ;
f[i][j] = f[i - ][j - ];
}
else if (d[i - ][j] > d[i][j - ])
{
d[i][j] = d[i - ][j];
f[i][j] = f[i - ][j];
}
else if (d[i - ][j] < d[i][j - ])
{
d[i][j] = d[i][j - ];
f[i][j] = f[i][j - ];
}
else
{
d[i][j] = d[i - ][j];
f[i][j] = f[i - ][j] + f[i][j - ];
}
}
printf("Case #%d: %d %lld\n", ++kase, len1 + len2 - d[len1][len2], f[len1][len2]);
}
return ;
}