Advertisement
juyana

uva 10066

May 27th, 2018
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.72 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #include<cstdio>
  3. using namespace std;
  4.  
  5. int a[105],b[105],dp[105][105];
  6. int n,m;
  7.  
  8. int LCS(int i, int j)
  9. {
  10. if(i==n||j==m) return 0;
  11. if(dp[i][j]!=-1) return dp[i][j];
  12. if(a[i]==b[j]) return dp[i][j]=1+LCS(i+1,j+1);
  13. int x,y;
  14. x=LCS(i+1,j);
  15. y=LCS(i,j+1);
  16. return dp[i][j]=max(x,y);
  17. }
  18.  
  19. int main()
  20. {
  21. int kase=0;
  22. while(1)
  23. {
  24. memset(dp,-1,sizeof dp);
  25. scanf("%d%d",&n,&m);
  26. if(n==0&&m==0) break;
  27. for(int i=0; i<n; i++)
  28. scanf("%d",&a[i]);
  29. for(int i=0; i<m; i++)
  30. scanf("%d",&b[i]);
  31. int ans=LCS(0,0);
  32. printf("Twin Towers #%d\nNumber of Tiles : %d\n",++kase,ans);
  33.  
  34.  
  35. }
  36. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement