#include<bits/stdc++.h> #define INF 1e9+7 using namespace std; pair<int, int> dp[50100][2]; int t[50100]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin>>n; for(int i=0;i<n;i++) cin>>t[i]; dp[0][0] = {t[0], 0}; dp[0][1] = {t[0], 0}; for(int i=1;i<n;i++) { if(t[i] > dp[i-1][0].first) dp[i][1] = {t[i], dp[i-1][0].second}; else dp[i][1] = {INF, dp[i-1][0].second+1}; if(t[i] < dp[i-1][1].first) dp[i][0] = {t[i], dp[i-1][1].second}; else dp[i][0] = {-INF, dp[i-1][1].second+1}; } cout<<min(dp[n-1][0].second, dp[n-1][1].second); }
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 | #include<bits/stdc++.h> #define INF 1e9+7 using namespace std; pair<int, int> dp[50100][2]; int t[50100]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin>>n; for(int i=0;i<n;i++) cin>>t[i]; dp[0][0] = {t[0], 0}; dp[0][1] = {t[0], 0}; for(int i=1;i<n;i++) { if(t[i] > dp[i-1][0].first) dp[i][1] = {t[i], dp[i-1][0].second}; else dp[i][1] = {INF, dp[i-1][0].second+1}; if(t[i] < dp[i-1][1].first) dp[i][0] = {t[i], dp[i-1][1].second}; else dp[i][0] = {-INF, dp[i-1][1].second+1}; } cout<<min(dp[n-1][0].second, dp[n-1][1].second); } |