給你一個數組，最多可以修改一個數，問最少的山峰和山谷數量之和。

小菜雞做了一年。
一上來想猜個結論，讓每個數等于其相鄰的兩個數，看了題解之后也證明的正確性，當時直接寫就沒后面這么多事了。
但是命運讓我分情況討論(逃。
畫了一張紙的圖，讓后面向樣例編程。終于是把分類討論的方法給過掉了。。。太麻煩就不講啦，直接貼一個題解的思路的代碼吧。

//#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid (tr[u].l+tr[u].r>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;int n; int a[N],c[N];bool get(int a[],int x) {if(x<=1||x>=n) return 0;if(a[x]>a[x-1]&&a[x]>a[x+1]||a[x]<a[x-1]&&a[x]<a[x+1]) return 1;return 0; }int main() { // ios::sync_with_stdio(false); // cin.tie(0);int _; scanf("%d",&_);while(_--){scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]),c[i]=a[i];int ans=0,sum=0;if(n<=3) { puts("0"); continue; }for(int i=2;i<=n-1;i++) if(get(a,i)) ans++,sum++;for(int i=1;i<=n;i++){int t=a[i];a[i]=a[i-1];ans=min(ans,sum-get(c,i)-get(c,i-1)-get(c,i+1)+get(a,i)+get(a,i-1)+get(a,i+1));a[i]=a[i+1];ans=min(ans,sum-get(c,i)-get(c,i-1)-get(c,i+1)+get(a,i)+get(a,i-1)+get(a,i+1));a[i]=t;}printf("%d\n",ans);}return 0; } /**/

分類討論：

//#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid (tr[u].l+tr[u].r>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;int n; int a[N],c[N];int main() { // ios::sync_with_stdio(false); // cin.tie(0);//rd_wa();int _; scanf("%d",&_);while(_--){//int id; scanf("%d",&id);//printf("%d\n",id);scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);// 1 谷 2峰int ans=0,sum;for(int i=2;i<=n-1;i++)if(a[i]>a[i-1]&&a[i]>a[i+1]) c[i]=2,ans++;else if(a[i]<a[i-1]&&a[i]<a[i+1]) c[i]=1,ans++;else c[i]=0;sum=ans;if(c[2]||c[n-1]) ans--;for(int i=2;i<=n-1;i++){if(c[i]){ans=min(ans,sum-1);if(c[i-1]&&!c[i+1]){if(c[i-1]==2&&a[i+1]>=a[i-1]||(i+1==n||a[i+1]==a[i+2])) ans=min(ans,sum-2);if(c[i-1]==1&&a[i+1]<=a[i-1]||(i+1==n||a[i+1]==a[i+2])) ans=min(ans,sum-2);}if(c[i+1]&&!c[i-1]){if(c[i+1]==2&&a[i-1]>=a[i+1]||(i-1==1||a[i-1]==a[i-2])) ans=min(ans,sum-2);if(c[i+1]==1&&a[i-1]<=a[i+1]||(i-1==1||a[i-1]==a[i-2])) ans=min(ans,sum-2);}}//else if(c[i-1]||c[i+1]) ans=min(ans,sum-1);if(c[i-1]&&c[i+1]&&c[i-1]==c[i+1]) ans=min(ans,sum-3);else if(c[i-1]&&c[i+1]) ans=min(ans,sum-1);}printf("%d\n",ans);for(int i=1;i<=n;i++) c[i]=0;}return 0; } /* 1 14 62 47 35 39 42 54 60 90 41 80 80 74 67 42 */

總結

以上是生活随笔為你收集整理的Hills And Valleys CodeForces - 1467B 思维的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。