SHARE
TWEET

Untitled

a guest Sep 23rd, 2019 77 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //Reducing LCS to LIS
  2. //https://www.spoj.com/problems/XMEN/
  3. //Leia https://stackoverflow.com/questions/34656050/reducing-longest-common-subsequence-to-longest-increasing-subsequence
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6.  
  7. int32_t main(){
  8.     ios::sync_with_stdio(false); cin.tie(0);
  9.     int nteste;
  10.     cin >> nteste;
  11.     while(nteste--){
  12.         int n;
  13.         cin >> n;
  14.         vector<int> s3(n+1), posicao_em_s1(n+1), dp;
  15.         int x;
  16.         for(int i = 1; i <= n; ++i){ //recebe s1
  17.             cin >> x;
  18.             posicao_em_s1[x] = i;
  19.         }
  20.         for(int i = 1; i <= n; ++i){ //recebe s2
  21.             cin >> x;
  22.             s3[i] = posicao_em_s1[x];
  23.         }
  24.         dp.push_back(s3[1]);
  25.         for(int i = 2; i <= n; ++i){
  26.             if(s3[i] > dp.back())
  27.                 dp.push_back(s3[i]);
  28.             else
  29.                 *lower_bound(dp.begin(), dp.end(), s3[i]) = s3[i];
  30.         }
  31.         cout << dp.size() << '\n';
  32.     }
  33. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top