1110 - An Easy LCS PDF (English) Statistics ForumTime Limit: 2 second(s) Memory Limit: 32 MBLCS means 'Longest Common Subsequence' that means two non-empty strings are given; you have to find the Longest Common Subsequence between them. Since there can be many solutions, you have to print the one which is the lexicographically smallest. Lexicographical order means dictionary order. For example, 'abc' comes before 'abd' but 'aaz' comes before 'abc'.
InputInput starts with an integer T (≤ 100), denoting the number of test cases.
Each case starts with a blank line. The next two lines will contain two strings of length 1 to 100. The strings contain lowercase English characters only.
OutputFor each case, print the case number and the lexicographically smallest LCS. If the LCS length is 0 then just print ':('.
Sample InputOutput for Sample Input3abbazxcvbnhjgasbznxbzmxyoukjhsCase 1: aCase 2: zxbCase 3: :(
解题思路: 用LCS的模板 加上记录路径就可以了。
但在做这题的过程中提交一直RE， 本地运行没问题。 仔细找之后才发现自己是从i=0，j=0开始遍历的，出现dp[i-1][j-1]的情况就RE，但是dev 不爆:(
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; const int N = 110; int dp[N][N]; char str1[N],str2[N],ans[N][N][N]; int main(){ int T; scanf("%d",&T); for(int t=1;t<=T;t++){ memset(dp,0,sizeof(dp)); memset(ans,0,sizeof(ans)); scanf("%s %s",str1+1,str2+1); int len1 = strlen(str1+1),len2 = strlen(str2+1); for(int i=1;i<=len1;i++){ for(int j=1;j<=len2;j++){ if(str1[i]==str2[j]){ dp[i][j] = dp[i-1][j-1] + 1; strcpy(ans[i][j],ans[i-1][j-1]); ans[i][j][dp[i-1][j-1]] = str1[i]; ans[i][j][dp[i][j]] = '\0'; }else{ dp[i][j] = max(dp[i-1][j],dp[i][j-1]); if(dp[i-1][j]<dp[i][j-1]){ strcpy(ans[i][j],ans[i][j-1]); }else if(dp[i-1][j]>dp[i][j-1]){ strcpy(ans[i][j],ans[i-1][j]); }else{ if(strcmp(ans[i][j-1],ans[i-1][j])>0){ strcpy(ans[i][j],ans[i-1][j]); }else{ strcpy(ans[i][j],ans[i][j-1]); } } } } } if(strlen(ans[len1][len2])==0)printf("Case %d: :(\n",t);// strcpy(ans[len1-1][len2-1],":(\0"); else printf("Case %d: %s\n",t,ans[len1][len2]); } }
转载于:https://www.cnblogs.com/yuanshixingdan/p/5568826.html
相关资源：JAVA上百实例源码以及开源项目