本文共 1541 字，大约阅读时间需要 5 分钟。
最长公共子序列
Time Limit: 1000 ms Memory Limit: 32768 KiB
Problem Description
从一个给定的串中删去（不一定连续地删去）0个或0个以上的字符，剩下地字符按原来顺序组成的串。例如：“ ”，“a”，“xb”，“aaa”，“bbb”，“xabb”，“xaaabbb”都是串“xaaabbb”的子序列。（例子中的串不包含引号。）
编程求N个非空串的最长公共子序列的长度。限制：2<=N<=100；N个串中的字符只会是数字0，1，…，9或小写英文字母a，b，…，z；每个串非空且最多含100个字符；N个串的长度的乘积不会超过30000。
Input
文件第1行是一个整数T，表示测试数据的个数（1<=T<=10）。接下来有T组测试数据。各组测试数据的第1行是一个整数Ni，表示第i组数据中串的个数。各组测试数据的第2到N+1行中，每行一个串，串中不会有空格，但行首和行末可能有空格，这些空格当然不算作串的一部分。
Output
输出T行，每行一个数，第i行的数表示第i组测试数据中Ni个非空串的最长公共子序列的长度。
Sample Input
13abbccd
Sample Output
0
代码如下：
#include #include #include int max2(int a,int b){ if(a>b) return a; else return b;}int min2(int a,int b){ if(a =1;i--) index=index*len[i]+x[i]-1; //记忆化搜索 if(dp[index]>=0) return dp[index]; //判断是否所有串的最后一个字符都相等 for(i=2;i<=n;i++) if(s[1][x[1]-1]!=s[i][x[i]-1]) break; if(i>n) //如果都相等，则最大长度+1 { for(j=1;j<=n;j++) x[j]--; ret=LCS(x)+1; for(j=1;j<=n;j++) x[j]++; } else //否则，求删去某个字符串的最后一个字符之后得到的最大值 { ret=0; for(j=1;j<=n;j++) { x[j]--; int t=LCS(x); ret=max2(t,ret); x[j]++; } } dp[index]=ret; return ret;}int main(){ int t,i; int temp[105]; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%s",s[i]); len[i]=temp[i]=strlen(s[i]); } memset(dp,-1,sizeof(dp)); printf("%d\n",LCS(temp)); } return 0;}
转载地址：http://ikhwi.baihongyu.com/