Advertisement
Es7evam

f.cpp

May 6th, 2018
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.25 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define pb push_back
  4. #define mk make_pair
  5. #define fi first
  6. #define se second
  7. #define fastcin ios_base::sync_with_stdio(false)
  8.  
  9. typedef long long ll;
  10. const int INF = 0x3f3f3f3f;
  11. const double PI = acos(-1.0);
  12.  
  13. int v[200007];
  14. int lis[200007];
  15.  
  16.  
  17. /* Driver program to test above function */
  18. int main(){
  19.     int n;
  20.  
  21.     cin >> n;
  22.     for(int i=0;i<n;i++){
  23.         cin >> v[i];
  24.     }
  25.  
  26.     int i, j, max = 0;
  27.  
  28.     for (i = 0; i < n; i++ )
  29.         lis[i] = 1;
  30.  
  31.     // Bottom up
  32.     for (i = 1; i < n; i++ )
  33.         for (j = 0; j < i; j++ )
  34.             if (v[i] == v[j]+1 && lis[i] < lis[j] + 1){
  35.                 lis[i] = lis[j] + 1;
  36.             }
  37.  
  38.     int imax = 0;
  39.     int maxtam = 0;
  40.     for (i = 0; i < n; i++ )
  41.         if (maxtam < lis[i]){
  42.             imax = i;
  43.             maxtam = lis[i];
  44.         }
  45.  
  46.     vector <int> st;
  47.     int cur = maxtam;
  48.     for(int i=imax;cur>0;i--){
  49.         if(lis[i] == cur){
  50.             cur--;
  51.             st.pb(i);
  52.         }
  53.     }
  54.     cout << maxtam << endl;
  55. /*
  56.     for(int i=0;i<n;i++){
  57.         cout << lis[i] << " ";
  58.     }
  59.     cout << endl;
  60. */
  61.     for(int i=st.size()-1;i>=0;i--){
  62.         cout << st[i]+1 << " ";
  63.     }
  64.  
  65.     return 0;
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement