Advertisement
Josif_tepe

Untitled

Jun 13th, 2024
324
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.89 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int INF = 2e9;
  4. const int maxn = 2002;
  5. vector<pair<int, int>> v;
  6. int dp[maxn];
  7. int rec(int at) {
  8.   if(dp[at] != -1) {
  9.     return dp[at];
  10.   }
  11.   int res = 1;
  12.   for(int i = at + 1; i < v.size(); i++) {
  13.     if(v[at].second <= v[i].second) {
  14.       res = max(res, rec(i) + 1);
  15.     }
  16.   }
  17.   return dp[at] = res;
  18. }
  19. int main()
  20. {
  21.   ios_base::sync_with_stdio(false);
  22.   int t;
  23.   cin >> t;
  24.   while(t--) {
  25.     v.clear();
  26.     int n;
  27.     cin >> n;
  28.     vector<int> a(n), b(n);
  29.     for(int i = 0; i < n; i++) {
  30.       cin >> a[i];
  31.     }
  32.     for(int i = 0; i < n; i++) {
  33.       cin >> b[i];
  34.       v.push_back(make_pair(a[i], b[i]));
  35.     }
  36.     sort(v.begin(), v.end());
  37.     memset(dp, -1, sizeof dp);
  38.     int res = 0;
  39.     for(int i = 0; i < n; i++) {
  40.       res = max(res, rec(i));
  41.     }
  42.     cout << res << endl;
  43.   }  
  44.  
  45.     return 0;
  46. }
  47.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement