题解 P6510 【奶牛排队】
sukimo
2020-07-22 17:36:57
这道题思路不算太难想。题中的“左边最矮”“右边最高”等信息让我们考虑使用单调栈来快速处理。
首先用单调栈处理出每头奶牛左边第一个身高大于等于它的奶牛位置$+1$的位置（$le$数组）以及右边第一个身高小于等于它的奶牛位置$-1$的位置（$ri$数组）。为什么呢？这样做，我们就框定了每头奶牛分别作为合题奶牛组的左端点$A$和右端点$B$时，剩余的端点$B$，$A$可取的范围。接下来我们发现，若两只奶牛$i,j(i<j)$符合$ri[i]\ge j$且$le[j]\le i$，则它们定可以分别作为合题奶牛组的$A,B$端点。很好证。
接下来就用一个枚举，枚举每头奶牛作为端点$B(A$也可以$)$时的最大满足数。中间可以加一些技巧性的小剪枝加速。详见代码：
```
#include<bits/stdc++.h>
using namespace std;
const int MX=100005;int n,le[MX],ri[MX],cow[MX];struct STR{int pos,num;};stack<STR>stk;
STR pack(int pos,int num){STR a;a.pos=pos;a.num=num;return a;}
void stk_push1(){
for(int i=1;i<=n;i++){
while(!stk.empty()&&stk.top().num<cow[i])stk.pop();
le[i]=(stk.empty()?1:stk.top().pos+1);stk.push(pack(i,cow[i]));
}
}
void stk_push2(){
for(int i=n;i>=1;i--){
while(!stk.empty()&&stk.top().num>cow[i])stk.pop();
ri[i]=(stk.empty()?n:stk.top().pos-1);stk.push(pack(i,cow[i]));
}
}
int main(){
int max_cnt=0;scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&cow[i]);
stk_push1();while(!stk.empty())stk.pop();stk_push2();
for(int i=1;i<=n;i++)
for(int j=le[i];j<i;j++){
if(i-j+1<=max_cnt)break;
if(ri[j]>=i){max_cnt=max(max_cnt,i-j+1);break;}
}
printf("%d",max_cnt);
return 0;
}
```