Codeforces Round #669(Div.2) D(단일 큐 이동 dp)

제목:

n개의 기둥을 줄게. 첫 번째 기둥에서 n개의 기둥으로 뛰어야 돼. 적어도 몇 번은 뛰어야 돼.

한 기둥에서 다른 기둥으로 뛰어내릴 수 있는 조건은:

이 두 기둥은 그들 사이의 모든 기둥보다 엄격하다

이 두 기둥은 그들 사이의 모든 기둥보다 엄격하다

앞기둥이 뒷기둥으로 뛰어오른다

그중 하나를 만족하면 된다.

문제 풀이:

먼저 dp[i]는 첫 번째 기둥에서 iii 기둥으로 뛰어오르는 것을 대표하며 적어도 몇 번은 뛰어야 한다.우리 중 뒤에서 앞을 보면 세 번째 조건의 방정식은 dp[i]=dp[i-3-1]+1dp[i]=dp[i-1]+1dp[i]=dp[i-3]+1이다.

두 번째 조건으로 우리는 단조로운 창고로 점차 줄어드는 서열을 유지할 수 있다.만족하려면 두 기둥이 그들 사이의 모든 기둥보다 낮다. 왼쪽에 대해 우리는 단조롭게 줄어드는 서열을 유지했기 때문에 뒤의 기둥은 반드시 앞의 기둥보다 낮다. 그러면 오른쪽 기둥을 보면 오른쪽 기둥이 왼쪽 기둥의 뒤의 기둥보다 크면 그들이 중간의 모든 기둥보다 엄격하게 크면 이동할 수 있다는 것을 의미한다.

첫 번째 조건은 같은 이치이고 구체적으로 보면 코드

tips: 저는 단조로운 대기열로 단조로운 창고를 시뮬레이션합니다. c++의 deque를 할 수 있기 때문에 단조로운 창고와 단조로운 대기열을 쉽게 쓸 수 있습니다.

#include 

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]<<'
';
	return 0;
}