Saleh127

UVA 497 / DP - LIS

Nov 30th, 2021
754
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-11-30-22.28.59
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define get_lost_idiot return 0
  9. #define nl '\n'
  10.  
  11. int main()
  12. {
  13.     ios_base::sync_with_stdio(0);
  14.     cin.tie(0);
  15.     cout.tie(0);
  16.  
  17.  
  18.     int tt;
  19.     cin>>tt;
  20.  
  21.     cin.ignore();
  22.     cin.ignore();
  23.     for(int cs=1; cs<=tt; cs++)
  24.     {
  25.         vector<ll>lis,a,ans;
  26.         ll n,m,i,j,k,l;
  27.  
  28.         string x;
  29.  
  30.         while(getline(cin,x) && x!="")
  31.         {
  32.             a.push_back(stoi(x));
  33.         }
  34.  
  35.         ll dp[a.size()+2]= {0};
  36.  
  37.         dp[0]=1;
  38.  
  39.         lis.push_back(a[0]);
  40.  
  41.         l=1;
  42.         for(i=1; i<a.size(); i++)
  43.         {
  44.             if(a[i]>lis[lis.size()-1])
  45.             {
  46.                 l++;
  47.                 lis.push_back(a[i]);
  48.                 dp[i]=l;
  49.             }
  50.             else
  51.             {
  52.                 k=lower_bound(lis.begin(),lis.end(),a[i])-lis.begin();
  53.  
  54.                 lis[k]=a[i];
  55.  
  56.                 dp[i]=k+1;
  57.             }
  58.         }
  59.  
  60.         for(i=a.size()-1; i>=0; i--)
  61.         {
  62.             if(dp[i]==l)
  63.             {
  64.                 l--;
  65.                 ans.push_back(a[i]);
  66.             }
  67.         }
  68.  
  69.         cout<<"Max hits: "<<ans.size()<<nl;
  70.  
  71.         for(i=ans.size()-1; i>=0; i--)
  72.         {
  73.             cout<<ans[i]<<nl;
  74.         }
  75.  
  76.         if(cs!=tt) cout<<nl;
  77.  
  78.     }
  79.  
  80.     get_lost_idiot;
  81. }
  82.  
RAW Paste Data