單調棧優化DP [ROI 2018] Decryption
題意
要求把一個序列劃分成很多段，要求對于每段，最大值是末項，最小值是首項。
求最小劃分段數。
解法
我們貪心來思考，若我們要保證一直到 i 是合法的，左端點顯然是越往左越好，但是在全局上是并沒有這個性質的，所以考慮 dp;
用兩個單調棧，嚴格單調減的 stk1, 嚴格單調增的 stk2。
設 dp[i] 表示劃分完 1～i 的最小段數。
我們在嚴格單調減的棧頂往下一個就是我們最極限的往左的位置（先不考慮首項最小的性質）
之后在 stk2 upper_bound 一下這個位置，找到最極限往左的地方。
n log n 太美麗辣。
代碼↓
點擊查看代碼
#include <bits/stdc++.h>
using namespace std;
const int MN=1e6+116;
int stk1[MN], stk2[MN], dp[MN];
int a[MN], n, top1, top2;
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n; for(int i=1; i<=n; ++i) cin>>a[i];
for(int i=1; i<=n; ++i){
while(top1&&a[stk1[top1]]<=a[i]) --top1;
stk1[++top1]=i;
while(top2&&a[stk2[top2]]>a[i]) --top2;
stk2[++top2]=i;
dp[i]=dp[*upper_bound(stk2+1,stk2+top2+1,stk1[top1-1])-1]+1;
}
cout<<dp[n]<<'\n';
return 0;
}
浙公網安備 33010602011771號