#include <iostream>
#include <vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector<int> A(N, 0);
for (int i = 0; i < N; ++i) {
int a;
cin >> a;
A[i] = a;
}
int dp[4] = {0, 0, 1, 1};
// 0 -- UP no change
// 1 -- DOWN no change
// 2 -- UP MAX LIMIT
// 3 -- DOWN MIN LIMIT
for (int i = 1; i < N; ++i) {
int dp1[4] = {};
dp1[0] = dp[3];
if (A[i - 1] < A[i]) dp1[0] = min(dp1[0], dp[1]);
dp1[1] = dp[2];
if (A[i - 1] > A[i]) dp1[1] = min(dp1[1], dp[0]);
dp1[2] = min(dp[1], dp[3]) + 1;
dp1[3] = min(dp[0], dp[2]) + 1;
dp[0] = dp1[0];
dp[1] = dp1[1];
dp[2] = dp1[2];
dp[3] = dp1[3];
}
cout << min(min(min(dp[0], dp[1]), dp[2]), dp[3]) << "\n";
return 0;
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | #include <iostream> #include <vector> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector<int> A(N, 0); for (int i = 0; i < N; ++i) { int a; cin >> a; A[i] = a; } int dp[4] = {0, 0, 1, 1}; // 0 -- UP no change // 1 -- DOWN no change // 2 -- UP MAX LIMIT // 3 -- DOWN MIN LIMIT for (int i = 1; i < N; ++i) { int dp1[4] = {}; dp1[0] = dp[3]; if (A[i - 1] < A[i]) dp1[0] = min(dp1[0], dp[1]); dp1[1] = dp[2]; if (A[i - 1] > A[i]) dp1[1] = min(dp1[1], dp[0]); dp1[2] = min(dp[1], dp[3]) + 1; dp1[3] = min(dp[0], dp[2]) + 1; dp[0] = dp1[0]; dp[1] = dp1[1]; dp[2] = dp1[2]; dp[3] = dp1[3]; } cout << min(min(min(dp[0], dp[1]), dp[2]), dp[3]) << "\n"; return 0; } |
English