SHARE
TWEET

Untitled

a guest Feb 20th, 2019 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int INF=1e9;
  5. int h[1010],dp[1010];
  6. int main()
  7. {
  8.     int n;
  9.     scanf("%d",&n);
  10.     for(int i=1;i<=n;++i){
  11.         scanf("%d",&h[i]);
  12.     }
  13.     /*int ans=-1e9;
  14.     for(int i=n;i>=1;--i){
  15.         for(int j=n+1;j>i;--j){
  16.             if(h[j]<=h[i])
  17.                 dp[i]=max(dp[i],1+dp[j]);
  18.         }
  19.         ans=max(ans,dp[i]);
  20.     }*/
  21.     /*h[0]=1e9;
  22.     int ans = 0;
  23.     for (int i = 1; i <= n; ++i) {
  24.         for (int j = 0; j < i; ++j) {
  25.             if (h[j] >= h[i])
  26.                 dp[i] = max(dp[i], dp[j]+1);
  27.         }
  28.         ans = max(ans, dp[i]);
  29.     }*/
  30.     int ans=0;
  31.     for (int i = 1; i <= n; ++i) {
  32.         dp[i] = 1;
  33.         for (int j = 1; j < i; ++j) {
  34.             if (h[j] >= h[i])
  35.                 dp[i] = max(dp[i], dp[j]+1);
  36.         }
  37.         ans = max(ans, dp[i]);
  38.     }
  39.     printf("%d",n-ans);
  40.     return 0;
  41. }
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