当前位置:   article > 正文

HDU 1506(单调栈)_hdu1506

hdu1506

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1506

 

题目大意:给n个矩阵的高度,问图中最大的矩阵能有多大

 

题目思路:如果在矩阵保持递增的情况下,那很容易就可以看出,得出最大面积的方法是,用最左的矩阵高度*整个矩阵的宽度,然后第二个*(整个矩阵宽度-1)以此类推。但是如果出现递减,我们也可以发现,前面的矩阵高于当前矩阵的部分都没用了,因为即使后面很高,有这个矮矩阵插在中间,他们也没办法合作,所以直接把前面比这个矮矩阵高的矩阵全合并成一个宽度为width,高度为这个矮矩阵高度的矩形,这样又恢复成了递增状态。将a[n+1]设成0就能保证最后一位出现递减使最后残余矩阵可以得到计算。

 

以下是代码:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define inf 0x3f3f3f3f
  4. #define MAXN 100005
  5. #define rep(i,a,b) for(int i=a;i<=b;i++)
  6. #define per(i,a,b) for(int i=a;i>=b;i--)
  7. #define ll long long
  8. int s[MAXN],a[MAXN],w[MAXN];
  9. int main(){
  10. int n,p;
  11. while(~scanf("%d",&n)&&n){
  12. rep(i,1,n)scanf("%d",&a[i]);
  13. a[n+1]=p=0;
  14. ll ans=0;
  15. rep(i,1,n+1){
  16. if(s[p]<a[i]){
  17. s[++p]=a[i];
  18. w[p]=1;
  19. }
  20. else{
  21. int width=0;
  22. while(s[p]>=a[i]&&p){
  23. width+=w[p];
  24. ans=max(ans,(ll)width*s[p]);
  25. p--;
  26. }
  27. s[++p]=a[i],w[p]=width+1;
  28. }
  29. }
  30. printf("%lld\n",ans);
  31. }
  32. return 0;
  33. }

 

声明:本文内容由网友自发贡献,转载请注明出处:【wpsshop】
推荐阅读
相关标签
  

闽ICP备14008679号