Discrete Centrifugal Jumps

这个题挺简单的(2333).
首先我们想一个问题.假如这个题的算法是(单调栈+dp),那应该怎么做才能ac.
单调栈无非就是维护一个单调序列,因为跳跃方式只有两种,如下图:

而单调栈维护的是一种序列的单调性,我们很容易知道,假如我维护的序列是从后往前单调递减的,那么转移肯定只能在两个栈头和这个之间转移,同理,假如我维护的序列是从后往前单调递增的,那么转移肯定只能在两个栈头和这个之间转移.如此就是一个**题了(不是)
代码如下:

#include <bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int a[N];
int dp[N];
stack<int>stk1,stk2;//1 递增,2 递减
int main()
{
    int n;
    scanf("%d",&n);
    memset(dp,0x3f,sizeof dp);
    dp[n]=0;stk1.push(n);stk2.push(n);
    for(int i=1;i<=n;i++)   scanf("%d",&a[i]);
    for(int i=n-1;i>=1;i--)
    {
        while(stk1.size()&&a[i]<a[stk1.top()])
        {
            dp[i]=min(dp[i],dp[stk1.top()]+1);
            stk1.pop();
        }
        if(stk1.size())
        {
            dp[i]=min(dp[i],dp[stk1.top()]+1);
            if(a[stk1.top()]==a[i]) stk1.pop();
        }
        stk1.push(i);
        while(stk2.size()&&a[i]>a[stk2.top()])
        {
            dp[i]=min(dp[i],dp[stk2.top()]+1);
            stk2.pop();
        }
        if(stk2.size())
        {
            dp[i]=min(dp[i],dp[stk2.top()]+1);
            if(a[stk2.top()]==a[i]) stk2.pop();
        }
        stk2.push(i);
    }
    printf("%d\n",dp[1]);
    return 0;
}

有个注意点,就是假如相同的话.要去掉栈头.