#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; } |