Discrete Centrifugal Jumps(单调栈+dp)

2020/09/11 15:21

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

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;

h[i]：4 3  2 5  这样的楼高度

i  :   1 2  3 4

#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;
}



0
0 收藏

0 评论
0 收藏
0