题目链接:https://www.luogu.org/problemnew/show/SP1805

分析:


我们可以用一个单调栈由低到高来存储它的高度,并用数组对每个高度记录一下它前面(包括它自己)一共有多少个比它高的,可以看做它的左宽。

按顺序考虑每个高度h,如果h大于栈顶元素,则入栈,此时它大于左面全部的元素,并且将它的宽度初始为1。

否则,将栈内元素出栈,直到满足上面的条件。出栈时,我们要将出栈元素对之后问题的影响全部考虑进行处理,才能保证做法的正确性。

对于每个高度,它的作用无非两个:

1、以自己作高,向外扩展

2、以别人作高,自己被扩展

由于我们数组中已经记录了某个高度的左宽,所以我们只需要考虑它能不能向右扩展,如果能,能扩展多少?

首先,对于第一个出栈的元素来说,它的右宽一定是0。

然而对于第二个,它的右边有刚才出栈的元素,而且刚才出栈元素的总宽中所涉及的元素一定可以被自己扩展,所以自己的右宽为刚才出栈元素的总宽。

同理可知,第三个出栈元素的右宽为第二个出栈元素的总宽。依次类推。

而当h大于栈顶元素时,h的左宽应该是上次出栈元素的总宽+1(自己),然后入栈。

最后时,将所有元素出栈,即可将所有情况考虑。

代码.吹泡泡cpp

#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
struct ben
{
    long long h,w;
}a[100005];
long long n,h[200005],ans;
void ddz()
{
    ans=0;
    int top=0;
    h[n+1]=0;
    for(int i=1;i<=n+1;i++)
    {
       	if(h[i]>a[top].h)
       	{
       		a[++top].h=h[i];
       		a[top].w=1;
       	}
    	else
        {
            long long qaq=0;
            while(a[top].h>h[i])
            {
                qaq+=a[top].w;
                ans=fmax(ans,qaq*a[top].h);
                top--;
            }
            a[++top].h=h[i];
            a[top].w=qaq+1;
        }
    }
    printf("%lld\n",ans); 
}
int main()
{
    while(1)
    {
        scanf("%lld",&n); 
        if(n==0)
			break;
        memset(h,0,sizeof(h));
        for(int i=1;i<=n;i++)
            scanf("%lld",&h[i]);
        ddz();
    }
   	return 0;
}
额,和楼下一位大佬的代码很像啊