Submission #1242366

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
const int MAX = (1e5)+1;

int n, pre, dp[MAX][2];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> pre;
	dp[0][0] = dp[0][1] = 1;
	for(int i = 1, x; i < n; i++) {
		cin >> x;
		if(pre < x) {
			dp[i][0] = min(dp[i-1][0], dp[i-1][1]+1);
			dp[i][1] = min(dp[i-1][0], dp[i-1][1])+1;
		} else if(pre > x) {
			dp[i][0] = min(dp[i-1][0], dp[i-1][1])+1;
			dp[i][1] = min(dp[i-1][1], dp[i-1][0]+1);
		} else {
			dp[i][0] = min(dp[i-1][0], dp[i-1][1]+1);
			dp[i][1] = min(dp[i-1][1], dp[i-1][0]+1);
		}
		pre = x;
	}
	cout << min(dp[n-1][0], dp[n-1][1]);
}

Submission Info

Judge Result