poj2250-打印单一LCS路径。

前端之家收集整理的这篇文章主要介绍了poj2250-打印单一LCS路径。前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

题目连接

题意:就是一个最长公共子序列。并打印其路径。

分析:最长公共子序列还不难,注意是打印它的一条路径。我们知道是用二维数组dp来保存它的匹配数。一旦有匹配的它就修改后面的值,保证了

如何一个状态当前的dp数据中是最大的值。看一张经典的图:


显示了路径的回溯。帮助我们能找到匹配的的过程。

为了记录它转移的方向。我们需要用辅助数组map来记录它是有那个状态转移而来的。可以用递归来实现。

代码如下:

  1. #include<cstdio>
  2. #include<cstring>
  3. //using namespace std;
  4.  
  5. int dp[105][105],map[105][105];
  6. char s[100][35],t[100][35];
  7.  
  8. void LCS(int a,int b)
  9. {
  10. for(int i=1;i<=a;i++)
  11. for(int j=1;j<=b;j++)
  12. if(strcmp(s[i-1],t[j-1])==0)
  13. {
  14. dp[i][j]=dp[i-1][j-1]+1;
  15. map[i][j]=1;
  16. }
  17. else{
  18. if(dp[i-1][j]>=dp[i][j-1])
  19. {
  20. map[i][j]=2;
  21. dp[i][j]=dp[i-1][j];
  22. }
  23. else
  24. {
  25. map[i][j]=3;
  26. dp[i][j]=dp[i][j-1];
  27. }
  28. }
  29. }
  30.  
  31. void path(int a,int b) //打印LCS路径
  32. {
  33. if(a==0||b==0) return;
  34. if(map[a][b]==1){
  35. path(a-1,b-1);
  36. printf("%s ",s[a-1]);
  37. }
  38. else if(map[a][b]==2)
  39. path(a-1,b);
  40. else
  41. path(a,b-1);
  42. }
  43.  
  44. int main()
  45. {
  46. int i,j,len1,len2;
  47. while(scanf("%s",s[0])!=EOF)
  48. {
  49. //memset(dp,sizeof(dp));
  50. for(len1=1;;len1++)
  51. {
  52. scanf("%s",s[len1]);
  53. if(strcmp(s[len1],"#")==0) break;
  54. }
  55. for(len2=0;;len2++)
  56. {
  57. scanf("%s",t[len2]);
  58. if(strcmp(t[len2],"#")==0) break;
  59. }
  60. LCS(len1,len2);
  61. path(len1,len2);
  62. printf("\n");
  63. }
  64. return 0;
  65. }

猜你在找的设计模式相关文章