solution-code1132

1
#include <iostream>
2
#include <cstdio>
3
#include <cstring>
4
#include <algorithm>
5
using namespace std;
6
int a[50005],f[50005],g[50005];
7
///f[i]:以a[i]元素结尾的末端状态为上升
8
///g[i]:以a[i]元素结尾的末端状态为下降
9
int main(void)
10
{
11
  int i,n;
12
  scanf("%d",&n);
13
  for(i=1;i<=n;++i)scanf("%d",&a[i]);
14
  f[1]=g[1]=1;
15
  for(i=2;i<=n;++i)
16
  {
17
    if(a[i-1]<a[i])
18
    {
19
      f[i]=max(f[i-1],g[i-1]+1);
20
      g[i]=g[i-1];
21
    }
22
    if(a[i-1]==a[i])
23
    {
24
      f[i]=f[i-1];g[i]=g[i-1];
25
    }
26
    if(a[i-1]>a[i])
27
    {
28
      f[i]=f[i-1];
29
      g[i]=max(f[i-1]+1,g[i-1]);
30
    }
31
  }
32
  printf("%d\n",n-max(f[n],g[n]));
33
  return 0;
34
}