@lkrabc
  • 板块灌水区
  • 楼主__Eun__
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/9 19:41
  • 上次更新2024/7/9 19:42:08
查看原帖
@lkrabc
1235464
__Eun__楼主2024/7/9 19:41

#include<bits/stdc++.h> using namespace std;int n,a[300005],dp[300005],top1,top2,stk1[300005],stk2[300005];int main(){scanf("%d",&n);for(int i = 1; i <= n; i++) scanf("%d",&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[*lower_bound(stk2+1,stk2+top2+1,stk1[top1-1])-1] + 1;}printf("%d",dp[n]);return 0;}

2024/7/9 19:41
加载中...