Longest Increasing Sequence + dp

Revision en2, by algoskipper, 2024-07-15 16:27:54

Can anyone hep me with this question I can think of LIS but am not able to solve it

Code implement with LIS

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(n) for(ll i=0;i<n;i++)
int main(){
  #ifndef ONLINE_JUDGE
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
#endif
ll t;
cin>>t;
while(t--){

    ll n;cin>>n;
    vector<pair<ll,ll>>a(n);
   f(n)cin>>a[i].first;
   f(n){cin>>a[i].second;}
   sort(a.begin(),a.end(),[&](pair<ll,ll>a,pair<ll,ll>b){
    if(a.first==b.first)return a.second>b.second;
    return a.first<b.first;
   });
   vector<ll>b;
   vector<pair<ll,ll>>lp;
   ll ans=1;
   lp.push_back({-1,-1});
   b.push_back(-1);
   for(ll i=0;i<n;i++){
if(lp[lp.size()-1].first==a[i].first)continue;
 auto it= lower_bound(b.begin(), b.end(), a[i].second);
        if (it == b.end()) {
            b.push_back(a[i].second);
            lp.push_back(a[i]);
        }
        else {
          lp[it-b.begin()]=a[i];
            b[it-b.begin()] = a[i].second;
        }
}    
       cout<<lp.size()-1<<endl;
}
}

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English algoskipper 2024-07-15 16:27:54 1052
en1 English algoskipper 2024-07-15 09:18:22 263 Initial revision (published)