題目鏈接：點擊查看
題目大意：給出 n 個大樓的高度記為 h，現在需要從第一個大樓到達第 n 個大樓，問最小步數是多少，只有滿足以下條件時才能從 i 移動到 j ，設 i < j：
題目分析：無后效性的最優解，顯然是 dp 問題，但又不好直接進行轉移，所以需要借助資料結構來維護
首先第一種情況的狀態不用多說了，直接轉移就好，對于后兩種情況，假設從狀態 dp[ i ] 轉移到 dp[ j ] ，對于每個接受狀態的 j 來說，需要找到一個 i ，滿足其之間的數都要小于 h[ i ] 和 h[ j ] 或者大于 h[ i ] 和 h[ j ] ，其實這就用到了單調堆疊的一個性質，先稍微回顧一下單調堆疊，假如現在維護了一個非嚴格遞增的單調堆疊（維護的是下標，其對應的高度嚴格遞增），一個比較明顯的結論就是，假如遍歷到當前的位置為 cur，那么對于單調堆疊內的高度 h 大于等于 cur 的位置 pos 來說，( pos , cur ) 開區間內的數一定都大于 h[ pos ]，假設 ( pos , cur ) 記憶體在一個數 x 小于等于 h[ pos ]，由于維護的是非嚴格遞增的堆疊，在之前遍歷到 x 時，會將大于等于 x 的 數包括 h[ pos ] 直接彈出堆疊，所以與假設矛盾，故 ( pos , cur ) 內的數一定都大于 h[ pos ] ，又因為這個 pos 我們一開始取得是 h[ pos ] >= h[ cur ] ，所以滿足了情況 3 ，也就是說明了 pos 的狀態是可以直接轉移到 cur 的狀態的，同理可證情況 2
那么如何實作呢，接上一段繼續說，如果到了位置 cur 時，現在的目標是需要找到所有 h[ pos ] >= h[ cur ] 的 pos 進行狀態轉移，而思考一下維護單調堆疊的程序，是需要將所有大于等于 h[ cur ] 的元素彈出堆疊，這也就對應了上面的狀態轉移，所以在彈堆疊的時候維護一下 dp 就可以了
最后需要注意的一個細節是，因為單調堆疊維護的是一個非嚴格遞增的序列，顯然在彈堆疊的時候的轉移都是合法的，那么當維護好單調堆疊后，此時的堆疊頂是否合法呢，我們需要分情況討論一下：
- 如果在彈堆疊的時候，遇到了一個 h[ pos ] == h[ cur ] ，那么當彈完堆疊后，此時堆疊頂的位置到 cur 的位置之間一定是存在著一個位置 pos 使得 h[ pos ] == h[ cur ] 的，此時的堆疊頂無法給 cur 轉移狀態
- 如果沒有遇到的話，那么在彈完堆疊后，可以保證堆疊頂到 cur 之間的數都嚴格大于 h[ cur ]，證明還是和上面的反證法一樣，假設存在一個數 x ∈ [ 堆疊頂 , cur ] ，且 x 小于等于 h[ cur ] ，那么在之前維護單調堆疊的時候，堆疊頂早就被彈出去了，所以得證，此時堆疊頂是可以向 cur 位置進行狀態轉移的
理論比較復雜，但是代碼實作起來比較簡單，我是用 stl 的堆疊寫的，可能看起來比較繞一些
代碼：
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f;
const int N=3e5+100;
int h[N],dp[N];
stack<int>st1,st2;
int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.in.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);
memset(dp,inf,sizeof(dp));
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",h+i);
dp[1]=0;
st1.push(1);
st2.push(1);
for(int i=2;i<=n;i++)
{
bool flag1=false,flag2=false;
while(st1.size()&&h[st1.top()]>=h[i])
{
if(h[st1.top()]==h[i])
flag1=true;
dp[i]=min(dp[i],dp[st1.top()]+1);
st1.pop();
}
if(st1.size()&&!flag1)
dp[i]=min(dp[i],dp[st1.top()]+1);
while(st2.size()&&h[st2.top()]<=h[i])
{
if(h[st2.top()]==h[i])
flag2=true;
dp[i]=min(dp[i],dp[st2.top()]+1);
st2.pop();
}
if(st2.size()&&!flag2)
dp[i]=min(dp[i],dp[st2.top()]+1);
st1.push(i);
st2.push(i);
}
printf("%d\n",dp[n]);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/5833.html
標籤：其他
上一篇：21屆秋招快手前端面經