URAL/1346

来自"NOCOW"

啊，又是DP。

#include <cstdio>
#include <cstdlib>
int a,b,t[100001],f[100001],g[100001];
int min(int a,int b)  {  return a>b?b:a;  }
int main()
{
    scanf("%d%d",&a,&b);
    for (int i=a;i<=b;++i)
        scanf("%d",&t[i]);
    f[a]=g[a]=1;
    for (int i=a+1;i<=b;++i)
    {
        if (t[i] < t[i-1])
            f[i]=min(f[i-1],g[i-1])+1;
        else
            f[i]=f[i-1];
        if (t[i] > t[i-1])
            g[i]=min(f[i-1],g[i-1])+1;
        else
            g[i]=g[i-1];
    }
    printf("%d\n",min(f[b],g[b]));
    return 0;
}
//by zzy