题目：uva10723 - Cyborg Genes（LIS）

题目大意：给出两个字符串，要求的到一个新的字符串，它保持了两个字符串的字符的特征，也就是可以在这个字符串中找到前两个字符串的子序列，求这样的字符串的最短长度和有多少种这样的不同的字符串。

解题思路：LIS。首先先要找出最长的公共子序列，这样得到的新的字符串的长度才会是最小：l1 + l2 - l【1】【N】；

l[i][j] ：第一个字符串的前i个字符和第二个字符串的前j个字符的最长的公共子序列长度。

n[i][j]: 使得第一个字符串的前i个字符和第二个字符串的前j个字符形成最短的不同的新的字符串的数目。

s[i] == s[j] , l[i][j] = l[ i- 1][j - 1] + 1; n[i][j] = n[i- 1][j - 1] ;

s[i] != s[j] , l[i][j] = Max (l[i-1][j], l[i][j - 1]); if (l[i - 1][j] > l[i][ j- 1]) n[i][j] = n[i - 1][j];（因为是要最短的字符串的种类）反之则反之。相等的情况:n[i][j] = n[i-1][j] + n[i][j - 1];

初始化：l【i】【0】 = l【0】【j】 = 0； n【0】【j】 = n【i】【0】 = 1；

代码：

#include 
  
   
#include 
   
     const int N = 35; typedef long long ll; int l[N][N]; ll n[N][N]; char s1[N], s2[N]; int l1, l2; int Max (const int a, const int b) { return a > b? a: b; } void init () { l1 = strlen (s1); l2 = strlen (s2); memset (l, 0, sizeof (l)); for (int i = 0; i <= l1; i++) n[i][0] = 1; for (int i = 0; i <= l2; i++) n[0][i] = 1; } int main () { int t; scanf ("%d%*c", &t); for (int k = 1; k <= t; k++) { printf ("Case #%d:", k); gets (s1); gets (s2); init (); for (int i = 1; i <= l1; i++) { for (int j = 1; j <= l2; j++) { if (s1[i - 1] == s2[j - 1]) { l[i][j] = l[i - 1][j - 1] + 1; n[i][j] = n[i - 1][j - 1]; } else { l[i][j] = Max (l[i - 1][j], l[i][j - 1]); // printf ("%d %d %d %d %d\n", i, j, l[i - 1][j], l[i][j - 1], l[i][j]); if (l[i - 1][j] > l[i][j - 1]) n[i][j] = n[i - 1][j]; else if (l[i - 1][j] < l[i][j - 1]) n[i][j] = n[i][j - 1]; else n[i][j] = n[i][j - 1] + n[i - 1][j]; } } } printf (" %d %lld\n", l1 + l2 - l[l1][l2], n[l1][l2]); } return 0; }