MinhNGUYEN2k4

LIQ

Feb 4th, 2021 (edited)
221
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.63 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define sz(x) int(x.size())
  3. #define all(x) x.begin(),x.end()
  4. #define reset(x) memset(x, 0,sizeof(x))
  5. #define pb push_back
  6. #define mp make_pair
  7. #define fi first
  8. #define se second
  9. #define N 100005
  10. #define remain(x) if (x > MOD) x -= MOD
  11. #define ii pair<int, int>
  12. #define vi vector<int>
  13. #define vii vector< ii >
  14. #define bit(x, i) (((x) >> (i)) & 1)
  15. #define Task "test"
  16. #define int long long
  17.  
  18. using namespace std;
  19.  
  20. typedef long double ld;
  21.  
  22. int n, a[N];
  23.  
  24. void readfile()
  25. {
  26.     ios_base::sync_with_stdio(false);
  27.     cin.tie(0);cout.tie(0);
  28.     if (fopen(Task".inp","r"))
  29.     {
  30.         freopen(Task".inp","r",stdin);
  31.         //freopen(Task".out","w",stdout);
  32.     }
  33.     cin >> n;
  34.     for(int i=1; i<=n; i++) cin >> a[i];
  35. }
  36.  
  37. int dp[N];
  38. int trace[N];
  39. int pos, Max = 0;
  40.  
  41. void truyvet()
  42. {
  43.     int s = pos;
  44.     stack<int> st;
  45.     while (s != 0)
  46.     {
  47.         st.push(s);
  48.         s = trace[s];
  49.     }
  50.     while (st.size())
  51.     {
  52.         cout << st.top() << ' ';
  53.         st.pop();
  54.     }
  55. }
  56.  
  57. void proc()
  58. {
  59.     memset(trace, -1, sizeof trace);
  60.     for(int i=1; i<=n; i++)
  61.     {
  62.         dp[i] = 0;
  63.         for(int j=0; j<i; j++){
  64.             if (a[j] <= a[i]){
  65.                 if (dp[i] <= dp[j] + 1)
  66.                 {
  67.                     dp[i] = dp[j] + 1;
  68.                     trace[i] = j;
  69.                 }
  70.             }
  71.         }
  72.     }
  73.     for(int i=1; i<=n; i++)
  74.     {
  75.         if (dp[i] > Max)
  76.         {
  77.             Max = dp[i];
  78.             pos = i;
  79.         }
  80.     }
  81.     cout << Max << '\n';
  82.     truyvet();
  83. }
  84.  
  85. signed main()
  86. {
  87.     readfile();
  88.     proc();
  89.     return 0;
  90. }
  91.  
Add Comment
Please, Sign In to add comment