CF1407D Discrete Centrifugal Jumps dp

题意：如图
思路：单调栈维护某个点的前驱节点有多少个，设置f[i]，定义为跳到i这个位置最少跳的次数。然后我们考虑一下什么时候可以跳 1：两边比中间都大，并且左边比右边大 2:两边比中间大，并且右边比左边大 3:两边比中间小，并且右边比左边大 4:两边比中间小，并且左边比右边大。维护四个单调栈。

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long ll;
#define pb push_back
const int N=300010;
int h[N];
int stk[N];	//左边比它大或者等于的第一个位置
int stk2[N];//左边比它小或者等于的第一个位置
int stk3[N];
int stk4[N];
int top;
int f[N];
vector<int>p[N];
int main()
{
   		
	int n;
	cin >> n ;
	for(int i=1;i<=n;i++)
		cin>>h[i];
	stk[top]=-1;
	for(int i=1;i<=n;i++)
	{
   
		while(top && h[stk[top]]<h[i])
			top--;
		p[i].pb(stk[top]);
		stk[++top]=i;
	}
	top=0;
	stk3[top]=-1;
	for(int i=n;i>=1;i--)
	{
   
		while(top && h[stk3[top]]<h[i])
			top--;
		if(stk3[top]!=-1)
		p[stk3[top]].pb(i);
		stk3[++top]=i;
	}
	top=0;
	stk4[top]=-1;
	for(int i=n;i>=1;i--)
	{
   
		while(top && h[stk4[top]]>h[i])
			top--;
		if(stk4[top]!=-1)
		p[stk4[top]].pb(i);
		stk4[++top]=i;
	}
	top=0;
	stk2[top]=-1;
	for(int i=1;i<=n;i++)
	{
   
		while(top && h[stk2[top]]>h[i])
			top--;
		p[i].pb(stk2[top]);
		stk2[++top]=i;
	}
	memset(f,0x3f,sizeof f);
	f[1]=0;
	for(int i=2;i<=n;i++)
	{
   
		f[i]=f[i-1]+1;
		for(auto x:p[i])
		{
   
			if(x==-1)
				continue;
			f[i]=min(f[i],f[x]+1);
		}
	}
	//cout<<f[7]<<endl;
	cout<<f[n]<<endl;
	return 0;

}