daily pastebin goal
6%
SHARE
TWEET

poldo

a guest Feb 6th, 2019 14 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <algorithm>
  3.  
  4. #define MAXN 10000
  5. #define max(a, b) ((a) > (b) ? (a) : (b))
  6.  
  7. int N;
  8. int P[MAXN], memo[MAXN];
  9.  
  10. int dp(int u, int prec) {
  11.     if(u >= N) return 0;
  12.     if(memo[u] != -1) return memo[u];
  13.     int yes = 0, no = dp(u+1, prec);
  14.     if(P[u] < prec) yes = dp(u+1, P[u])+1;
  15.     memo[u] = max(yes, no);
  16.     return memo[u];
  17. }
  18.  
  19. int main() {
  20.     freopen("input.txt", "r", stdin);
  21.     //freopen("output.txt", "w", stdout);
  22.     scanf("%d", &N);
  23.     for(int i = 0; i < N; i++) memo[i] = -1;
  24.     for(int i = 0; i < N; i++) scanf("%d", P+i);
  25.     dp(0, MAXN);
  26.     printf("%d", *std::max_element(memo, memo+N));
  27.     return 0;
  28. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top