Advertisement
Guest User

Untitled

a guest
Jul 28th, 2016
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.52 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.    
  3.    
  4. #define mp make_pair
  5. #define sz size()
  6. #define ull unsigned long long
  7. #define ll long long
  8. #define ld long double
  9. #define all(x) (x).begin(), (x).end()
  10. #define pb push_back
  11. #define sc second
  12. #define fs first
  13.    
  14. using namespace std;
  15.  
  16. const ll INF = 2000000000000000000;
  17.  
  18. vector<int> ans;
  19. int a[1001], b[1001], dp[1001][1001];
  20. int min3(int a, int b, int c) {
  21.     return min(min(a, b), c);
  22. }
  23.  
  24. void restore(int i, int j) {
  25.     if (i >= 0 && j >= 0) {
  26.         if (a[i] == b[j]) {
  27.             ans.pb(a[i]);
  28.             restore(i - 1, j - 1);
  29.         } else if (dp[i][j] == dp[i - 1][j])
  30.             restore(i - 1, j);
  31.         else
  32.             restore(i, j - 1);
  33.  
  34.     }
  35. }
  36.  
  37. int main() {
  38.     freopen("input.txt", "r", stdin);
  39.     freopen("output.txt", "w", stdout);
  40.     int n;
  41.     cin >> n;
  42.     for (int i = 0; i<n; i++)
  43.         cin >> a[i];
  44.     int m;
  45.     cin >> m;
  46.     for (int i = 0; i<m; i++)
  47.         cin >> b[i];
  48.     memset(dp, 0, sizeof(dp));
  49.     int s = 1000000000;
  50.     for (int i = 0; i<m; i++) {
  51.         if (a[0] == b[i]) {
  52.             s = i;
  53.             break;
  54.         }
  55.     }
  56.     for (int i = s; i<m; i++)
  57.         dp[0][i] = 1;
  58.     s = 1000000000;
  59.     for (int i = 0; i<n; i++) {
  60.         if (b[0] == a[i]) {
  61.             s = i;
  62.             break;
  63.         }
  64.     }
  65.     for (int i = s; i<n; i++)
  66.         dp[i][0] = 1;
  67.     for (int i = 1; i<n; i++)
  68.         for (int j = 1; j<m; j++) {
  69.             if (a[i] == b[j])
  70.                 dp[i][j] = dp[i - 1][j - 1] + 1;
  71.             else
  72.                 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
  73.         }
  74.     //cout << dp[n - 1][m - 1] << "\n";
  75.     restore(n - 1, m - 1);
  76.     reverse(all(ans));
  77.     for (int i = 0; i<ans.size(); i++)
  78.         cout << ans[i] << " ";
  79.     return 0;
  80. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement