Advertisement
double_trouble

послед

Nov 21st, 2014
164
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.52 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <cmath>
  5. #include <string>
  6. #include <algorithm>
  7. #include <string>
  8. #include <string.h>
  9.  
  10. #define F first
  11. #define S second
  12.  
  13.  
  14.  
  15. using namespace std;
  16.  
  17. int a[4010], b[4010], f[4010][4010];
  18. vector <int> k;
  19.  
  20. int main()
  21. {
  22.     ios_base::sync_with_stdio(0);
  23.     freopen("input.txt", "r", stdin);
  24.     freopen("output.txt", "w", stdout);
  25.     int n;
  26.     cin >> n;
  27.     for (int i = 1; i <= n; i++)
  28.         cin >> a[i];
  29.     int m;
  30.     cin >> m;
  31.     for (int i = 1; i <= m; i++)
  32.         cin >> b[i];
  33.     for (int i = 0; i <= n; i++)
  34.         for (int j = 0; j <= m; j++)
  35.         f[i][j] = 0;
  36.     for (int i = 1; i <= n; i++)
  37.         for (int j = 1; j <= m; j++)
  38.         if (a[i] == b[j])
  39.         f[i][j] = f[i - 1][j - 1] + 1;
  40.     else
  41.         f[i][j] = max(f[i - 1][j], f[i][j - 1]);
  42.     //cout << f[n][m] << endl;
  43.     int i = n;
  44.     int j = m;
  45.     /*for (int i = 0; i <= n; i++)
  46.         {
  47.             for (int j = 0; j <= m; j++)
  48.                 cout << f[i][j] << " ";
  49.             cout << endl;
  50.         }
  51.     */
  52.     while (f[i][j] != 0)
  53.     {
  54.         while (j > 1 && f[i][j] == f[i][j - 1])
  55.             j--;
  56.         if (a[i] == b[j])
  57.         {
  58.             k.push_back(a[i]);
  59.             j--;
  60.         }
  61.         else
  62.             if (i > 1)
  63.             i--;
  64.     }
  65.    /* for (int i = 0; i < k.size(); i++)
  66.         cout << k[i] << " ";
  67.     cout << endl;
  68.     */
  69.     for (int i = k.size() - 1; i >= 0; i--)
  70.     cout << k[i] << " ";
  71.     return 0;
  72. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement