构建电子商务网站的步骤,免费发布平台,zencart 网站安装,WordPress 嵌入flash给你一个数组#xff0c;最多可以修改一个数#xff0c;问最少的山峰和山谷数量之和。
小菜鸡做了一年。 一上来想猜个结论#xff0c;让每个数等于其相邻的两个数#xff0c;看了题解之后也证明的正确性#xff0c;当时直接写就没后面这么多事了。 但是命运让我分情况讨… 给你一个数组最多可以修改一个数问最少的山峰和山谷数量之和。
小菜鸡做了一年。 一上来想猜个结论让每个数等于其相邻的两个数看了题解之后也证明的正确性当时直接写就没后面这么多事了。 但是命运让我分情况讨论(逃。 画了一张纸的图让后面向样例编程。终于是把分类讨论的方法给过掉了。。。太麻烦就不讲啦直接贴一个题解的思路的代码吧。
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#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 pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n;
int a[N],c[N];bool get(int a[],int x)
{if(x1||xn) return 0;if(a[x]a[x-1]a[x]a[x1]||a[x]a[x-1]a[x]a[x1]) return 1;return 0;
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);int _; scanf(%d,_);while(_--){scanf(%d,n);for(int i1;in;i) scanf(%d,a[i]),c[i]a[i];int ans0,sum0;if(n3) { puts(0); continue; }for(int i2;in-1;i) if(get(a,i)) ans,sum;for(int i1;in;i){int ta[i];a[i]a[i-1];ansmin(ans,sum-get(c,i)-get(c,i-1)-get(c,i1)get(a,i)get(a,i-1)get(a,i1));a[i]a[i1];ansmin(ans,sum-get(c,i)-get(c,i-1)-get(c,i1)get(a,i)get(a,i-1)get(a,i1));a[i]t;}printf(%d\n,ans);}return 0;
}
/**/
分类讨论
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#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 pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-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 i1;in;i) scanf(%d,a[i]);// 1 谷 2峰int ans0,sum;for(int i2;in-1;i)if(a[i]a[i-1]a[i]a[i1]) c[i]2,ans;else if(a[i]a[i-1]a[i]a[i1]) c[i]1,ans;else c[i]0;sumans;if(c[2]||c[n-1]) ans--;for(int i2;in-1;i){if(c[i]){ansmin(ans,sum-1);if(c[i-1]!c[i1]){if(c[i-1]2a[i1]a[i-1]||(i1n||a[i1]a[i2])) ansmin(ans,sum-2);if(c[i-1]1a[i1]a[i-1]||(i1n||a[i1]a[i2])) ansmin(ans,sum-2);}if(c[i1]!c[i-1]){if(c[i1]2a[i-1]a[i1]||(i-11||a[i-1]a[i-2])) ansmin(ans,sum-2);if(c[i1]1a[i-1]a[i1]||(i-11||a[i-1]a[i-2])) ansmin(ans,sum-2);}}//else if(c[i-1]||c[i1]) ansmin(ans,sum-1);if(c[i-1]c[i1]c[i-1]c[i1]) ansmin(ans,sum-3);else if(c[i-1]c[i1]) ansmin(ans,sum-1);}printf(%d\n,ans);for(int i1;in;i) c[i]0;}return 0;
}
/*
1
14
62 47 35 39 42 54 60 90 41 80 80 74 67 42
*/
