Advertisement
yoyoboyss

Untitled

Feb 22nd, 2019
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.10 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int NMAX = 1024;
  5.  
  6. ifstream fin("cmlsc.in");
  7. ofstream fout("cmlsc.out");
  8.  
  9. int s1[NMAX], s2[NMAX], dp[NMAX][NMAX], sol[NMAX];
  10. int N1, N2, k;
  11.  
  12. int read(){
  13. fin >> N1 >> N2;
  14. for(int i = 1; i <= N1; i++)
  15. fin >> s1[i];
  16. for(int i = 1; i <= N2; i++)
  17. fin >> s2[i];
  18. }
  19.  
  20. int afisare(int v[NMAX], int N){
  21. for(int i = 1; i <= N; i++)
  22. fout << v[i] << ' ';
  23. }
  24.  
  25. int main(){
  26.  
  27. read();
  28.  
  29. for(int i = 1; i <= N1; i++){
  30. for(int j = 1; j <= N2; j++){
  31. if(s1[i] == s2[j])
  32. dp[i][j] = 1 + dp[i-1][j-1];
  33. else
  34. dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
  35. }
  36. }
  37.  
  38. int i = N1;
  39. int j = N2;
  40. while(dp[i][j]){
  41. if(s1[i] == s2[j]){
  42. sol[k++] = s1[i];
  43. i--; j--;
  44. } else {
  45. if(dp[i-1][j] > dp[i][j-1])
  46. i--;
  47. else
  48. j--;
  49. }
  50. }
  51.  
  52. fout << dp[N1][N2] << endl;
  53. while(k--)
  54. fout << sol[k] << ' ';
  55.  
  56. return 0;
  57. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement