Discrete Centrifugal Jumps(單調堆疊+dp)-有解無憂

https://codeforces.com/contest/1407/problem/D

首先定義dp[i]:當前共有i棟樓表示到第i棟樓的最小步數，

根據條件有如下轉移:

1.dp[i]=dp[i-1]+1;

2.i前面有一個下標假設為j，且這個j滿足(a[j]>max(a[j+1]......,a[i-1]); dp[i]=dp[j]+1;

3.i前面有一個下標假設為j,且這個j滿足(a[j]<min(a[j+1].......a[i-1]);dp[i]=dp[j]+1;

那么找這個j的程序用單調堆疊優化，

具體是什么意思呢？

比如現在有

h[i]：4 3 2 5 這樣的樓高度

i : 1 2 3 4

設一個down的單調堆疊，維護堆疊內的元素是單調遞減的，當遍歷到i=4的時候，由于h[4]>h[down.top() =(3) ] ,那么此時down堆疊的單調遞減性質破壞，需要不停down.pop(),使得堆疊里沒有比h[4]更校的，讓這個h[4]來當down堆疊此時的龍頭，

于是在pop()的程序中，最開始的down.top=3,但是這個是和i=4相鄰的，在轉移最開始我們就進行了dp[i]=dp[i-1]+1；所以這里其實無所謂第一個top的轉移，但是當第二個down.top()==2的時候,這時候進行dp[i]=min(dp[i],dp[down.top]+1)的轉移，如此往復到i=n的時候就維護好了，優化了不停找j的程序，

反之亦然

#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=3e5+100;
typedef long long LL;
LL h[maxn],dp[maxn];
int main(void)
{
  cin.tie(0);std::ios::sync_with_stdio(false);
  LL n;cin>>n;
  for(LL i=1;i<=n;i++){
  	cin>>h[i];
  }
  for(LL i=1;i<=n;i++) dp[i]=i;//初始化最大
  dp[1]=0;
  stack<LL>up,down;
  
  up.push(1);down.push(1);
  for(LL i=2;i<=n;i++){
  	dp[i]=dp[i-1]+1;//第一個轉移
	
	while(down.size()&&h[i]>=h[down.top()])
	{
		LL x=h[down.top()];
		down.pop();
		if(h[i]>x&&down.size())
		{
			dp[i]=min(dp[i],dp[down.top()]+1);	
		}	
	} 
	down.push(i);//當前的最高元素入隊 
	
	while(up.size()&&h[i]<=h[up.top()])
	{
		LL x=h[up.top()];
		up.pop();
		if(h[i]<x&&up.size())
		{
			dp[i]=min(dp[i],dp[up.top()]+1);
		}
	}
	up.push(i);
  }
  cout<<dp[n]<<endl;
return 0;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/7929.html

標籤：其他

上一篇：Android：觸摸移動的懸浮視窗

下一篇：Linux密碼忘了怎么辦？或者進入他人的Linux系統，我教你，拿去拿去別客氣，安排（也可進入別人的Linux搞一搞）！！！！