UVa 10723

题目链接：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1664

考察对于 (LCS) 的理解，最短字符串肯定是两串长度减去 (LCS) 的长度，而最短字符串的数量，也可以用类似 (LCS) 的方法求出

设 (f[i][j]) 表示第一个字符串前 (i) 个字符和第二个字符串前 (j) 个字符所得到的 (LCS)，(g[i][j]) 表示第一个字符串前 (i) 个字符和第二个字符串前 (j) 个字符所得到的最短字符串的数量，考虑当前 (LCS) 最后一个字符的位置

如果 (s[i] == t[j])，说明 (i,j) 是 (LCS) 的最后一个字符，(g[i][j] = g[i-1][j-1])，在上一个最短字符串后面添加一个字符，方案数不变

如果 (s[i] != t[j])，考虑 (LCS) 是从哪里转移过来的
如果 (f[i-1][j] > f[i][j-1])，则说明当前 (LCS) 最后一个字符之后只有一个不在 (LCS) 中的字符，因为字符间的相对位置不能改变，新添加的字符在最短字符串中必须在 (LCS) 最后一个字符之后，所以 (g[i][j] = g[i-1][j])，表示放置完 (LCS) 最后一个字符之后再添加新字符，反之亦然

而如果 (f[i-1][j] = f[i][j-1])，则说明当前 (LCS) 最后一个字符之后有不止一个不在 (LCS) 中的字符，这些字符的顺序随意，所以 (g[i][j] = g[i-1][j] + g[i][j-1])，表示这些字符所放的顺序无所谓

最后注意输入的字符串可能含有空格，所以要使用 (getline()) 函数读入

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 35;

int T, n, m;
int f[maxn][maxn], g[maxn][maxn];

ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); } return s * f; }

int main(){
	scanf("%d", &T);
	getchar();
	int kase = 0;
	while(T--){
		string a, b;
		getline(cin, a);
		getline(cin, b);
		n = a.length(), m = b.length();
		a = " " + a;
		b = " " + b;
		
		memset(f, 0, sizeof(f));
		memset(g, 0, sizeof(g));
		g[0][0] = 1;
		for(int i = 1 ; i <= max(n, m) ; ++i) g[i][0] = g[0][i] = 1; 
		for(int i = 1 ; i <= n ; ++i){
			for(int j = 1 ; j <= m ; ++j){
				if(a[i] == b[j]){
					f[i][j] = max(f[i][j], f[i-1][j-1] + 1);
					g[i][j] = g[i-1][j-1];
				} else{
					if(f[i-1][j] > f[i][j-1]){
						f[i][j] = max(f[i-1][j], f[i][j-1]);
						g[i][j] = g[i-1][j];
					} else if(f[i-1][j] < f[i][j-1]){
						f[i][j] = max(f[i-1][j], f[i][j-1]);
						g[i][j] = g[i][j-1];
					} else{
						f[i][j] = max(f[i-1][j], f[i][j-1]);
						g[i][j] = g[i-1][j] + g[i][j-1];
					}
				}
			}
		}
		
		printf("Case #%d: %d %d
", ++kase, n + m - f[n][m], g[n][m]);
	} 
	return 0;
}