Submission #1221348

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

int dp[100005][2];
int A[100005];
int N;
void upmin(int &a,int b){
  a = min( a, b );
}
const int INF = (1<<29);
int main() {
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> A[i];
    dp[i+1][0] = dp[i+1][1] = INF;
  }
  dp[0][0] = dp[0][1] = 1;
  for (int i = 1; i < N; i++) {
    if( A[i-1] <= A[i] ) upmin( dp[i][0], dp[i-1][0] );
    if( A[i-1] >= A[i] ) upmin( dp[i][1], dp[i-1][1] );
    upmin( dp[i][1], dp[i-1][0]+1 );
    upmin( dp[i][0], dp[i-1][1]+1 );
    upmin( dp[i][0], dp[i-1][0]+1 );
    upmin( dp[i][1], dp[i-1][1]+1 );
  }
  cout << min( dp[N-1][0], dp[N-1][1] ) << endl;
}

Submission Info

Judge Result