Advertisement
Ginger_samurai

Untitled

Feb 9th, 2020
135
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.64 KB | None | 0 0
  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. using namespace std;
  5. int main() {
  6.     int n;
  7.     cin >> n;
  8.     vector<int>a(n+1);
  9.     for (int i = 1; i <= n; i++) {
  10.         cin >> a[i];
  11.     }
  12.     int m;
  13.     cin >> m;
  14.     vector<int>b(m + 1);
  15.     for (int i = 1; i <= m; i++) {
  16.         cin >> b[i];
  17.     }
  18.     vector<vector<int> >dp(n + 1, vector<int>(m + 1));
  19.     for (int i = 1; i <= n; i++) {
  20.         dp[i][0] = 0;
  21.     }
  22.     for (int i = 1; i <= m; i++) {
  23.         dp[0][i] = 0;
  24.     }
  25.     for (int i = 1; i <= n; i++) {
  26.         for (int j = 1; j <= m; j++) {
  27.             if (a[i] == b[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
  28.             else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
  29.         }
  30.     }
  31.    
  32.     cout << dp[n][m];
  33. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement