Codeforces Round #669 (Div. 2) D （单调队列转移dp）

题意：

• 给你n根柱子，你在第一根柱子上，要跳到第n根柱子，问你最少要跳几下。
• 能从一根柱子跳到另外一根柱子的条件是：
  1. 这两根柱子严格比他们中间的所有柱子高
  2. 这两根柱子严格比他们中间的所有柱子低
  3. 前一根柱子跳到后一根柱子
  • 满足其中一个就可以了。

题解：

• 首先dp【i】代表的是从第一根柱子跳到第$i$根柱子上，最少要跳几下。我们中后往前看，那么第三个条件的方程是：$dp[i]=dp[i-1]+1$;
• 第2个条件，我们可以用单调栈维护一个递减的序列。要想满足，两根柱子比他们中间的所有柱子都低，对于左边，因为我们维护了一个单调递减的序列，后面的必然比前面的低，那么，看右端点，如果右端点大于左端点的后一个，那么就意味着，他们严格大于中间的所有柱子，就可以转移了。
• 第一个条件同理，具体看代码

tips：我是用单调队列模拟单调栈，因为会c++中的deque，就可以方便的写单调栈和单调队列了?。

#include <bits/stdc++.h>

using namespace std;
int dp[300005],a[300005];
int main() {
	int n;
	cin >> n;
	dp[0] = -1;
	deque<int>p,q;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		dp[i] = dp[i-1] + 1;
		while(q.size() && a[q.back()] <= a[i]) {
			int tmp = a[q.back()];
			q.pop_back();
			
			if(q.size() && tmp < a[i])
				dp[i] = min(dp[i],dp[q.back()] + 1);
			
		}
		q.push_back(i);
		
		while(p.size() && a[p.back()] >= a[i]) {
			int tmp = a[p.back()];
			p.pop_back();
			
			if(p.size() && tmp > a[i])
				dp[i] = min(dp[i],dp[p.back()] + 1);
			
		}
		p.push_back(i);
	}
	
	cout<<dp[n]<<'\n';
	return 0;
}