Advertisement
leminhkt

77

Sep 11th, 2020
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.88 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. const short LOVE = 1411;
  6. const int N = 1e3;
  7.  
  8.  
  9. int n;
  10. int a[N + 1];
  11.  
  12. int mem[N + 1];
  13. int trace[N + 1];
  14. bitset<N + 1> visited;
  15.  
  16.  
  17. void print(int n) {
  18.     if (trace[n] != n) print(trace[n]);
  19.     cout << a[n] << ' ';
  20. }
  21.  
  22.  
  23. int f(int n) {
  24.     if (n == 0) return 1;
  25.     if (visited[n]) return mem[n];
  26.     visited[n] = true; mem[n] = 1; trace[n] = n;
  27.     for (int i = 0; i < n; ++i)
  28.         if (a[i] < a[n] && mem[n] < f(i) + 1)
  29.             mem[n] = f(i) + 1,
  30.             trace[n] = i;
  31.     return mem[n];
  32. }
  33.  
  34.  
  35. void query() {
  36.     cin >> n;
  37.     for (int i = 0; i < n; ++i) cin >> a[i];
  38.     int k = 0;
  39.     for (int i = 1; i < n; ++i)
  40.         if (f(i) > f(k)) k = i;
  41.     cout << f(k) << '\n';
  42.     print(k);
  43. }
  44.  
  45.  
  46. int main(){
  47.     //freopen("Test.INP", "r", stdin);
  48.     //freopen("Test.OUT", "w", stdout);
  49.     cin.tie(NULL)->sync_with_stdio(false);
  50.  
  51.  
  52.     int t; for (t = 1; t--;) query();
  53.  
  54.  
  55.     return 0;
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement