注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

单调栈  

2015-06-29 23:44:59|  分类: ACM-poj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这里总结下单调栈,之前没接触过这种数据结构,查了资料后以为单调栈就是一个单调递增或者递减的栈,并不了解具体能解决什么问题,做了三道题后,对单调栈有所了解:
它可以求以某个值为最小值(或最大值),向两边扩展出一段连续区间,这个值在该区间内永远是最小值(或最大值)。
这个区间的左边界是栈顶前一个元素的位置+1;区间的右边界是当前位置-1.
注:只有出栈的元素是确定区间的。

poj3250:
题意:有n个高度不一致的牛排列在一起,求所有牛能向右边看到的牛数之和(高度小于该牛就能被看到,高度大于等于该牛的会挡住视线)
维护一个单调递减栈,遍历一遍即可,统计每个元素加入栈后的栈元素个数之和。
int n;
stack<int>s;

void solve()
{
int a;
LL ans=0;
while(!s.empty()) s.pop();
for(int i=0;i<n;i++)
{
sf(a);
while(!s.empty() && s.top() <= a)
s.pop();
ans+=s.size();
s.push(a);
}
pf64(ans);
}

int main()
{
while(sf(n)!=EOF)
solve();
return 0;
}

poj2559:
题意:有n个宽为1长度不一致的矩形连在一块,求能构成的的最大矩形面积,长度为其中一个矩形的长度。
也就是求某段区间的最小值*区间长度的最大值。
维护单调递增栈,按上面提到的,元素出栈时,求出区间长度*栈顶元素的最大值即可。
int n;
struct Node{
int id,num;
}node[100010];
stack<int>s;

void solve()
{
LL ans=0;
while(!s.empty()) s.pop();
node[0].id=0;node[0].num=-1;
s.push(0);
for(int i=1;i<=n;i++)
{
node[i].id=i;
sf(node[i].num);
while(!s.empty() && node[s.top()].num > node[i].num)
{
int tmp=s.top();
s.pop();
LL t=(LL)node[tmp].num*(LL)(i-1-node[s.top()].id);
ans=max(ans,t);
}
s.push(i);
}
while(!s.empty())
{
int tmp=s.top();
s.pop();
if(!s.empty())
{
LL t=(LL)node[tmp].num*(LL)(n-node[s.top()].id);
ans=max(ans,t);
}
}
printf("%lld\n",ans);
}

int main()
{
while(sf(n)!=EOF && n)
solve();
return 0;
}

poj2796:
题意:求某段区间的最小值*区间元素和的最大值,以及区间的左右边界。
维护单调递增栈,这题和上面一题差不多,元素出栈时,求出区间和(可以通过求区间边界求得)*栈顶元素的最大值,并记录边界位置。
int n,id[N],a[N];
stack<int>s;
LL sm[N];

void solve()
{
while(!s.empty()) s.pop();
sm[0]=0;a[0]=-1;id[0]=0;
for(int i=1;i<=n;i++)
{
sf(a[i]);
id[i]=i;
sm[i]=sm[i-1]+a[i];
}
int lef,rig;
LL ans=-1;
s.push(0);
for(int i=1;i<=n;i++)
{
while(!s.empty() && a[s.top()] > a[i])
{
int tt=s.top();
s.pop();
LL tmp=(LL)a[tt]*((LL)sm[i-1]-sm[id[s.top()]]);
if(tmp > ans)
{
ans=tmp;
rig=i-1;
lef=id[s.top()]+1;
}
}
s.push(i);
}
while(!s.empty())
{
int tt=s.top();
s.pop();
if(tt == 0)
break;
LL tmp=(LL)a[tt]*((LL)sm[n]-sm[id[s.top()]]);
if(tmp > ans)
{
ans=tmp;
rig=n;
lef=id[s.top()]+1;
}
}
printf("%lld\n%d %d\n",ans,lef,rig);
}

int main()
{
while(sf(n)!=EOF)
solve();
return 0;
}

  评论这张
 
阅读(193)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017