PKU 2082 Terrible Sets(单调栈)

一排紧密相连的矩形,求能构成的最大矩形面积。

为了防止栈为空,所以提前加入元素(0,0).

#include<cstdio>

#include<stack>

#define maxn 50005

using namespace std;

struct Element

{

    int length;

    int height;

    Element(){}

    Element(int _w,int _h){

        length=_w,height=_h;

    }

}e[maxn];

int n,curlength,curheight,curArea,maxArea;

stack<Element> S;

int get_Max()

{

    S.push(Element(,));

    maxArea=;

    for(int i=;i<=n;i++){

        curheight=e[i].height;

        curlength=;

        while(S.top().height>curheight){

            Element now=S.top();

            S.pop();

            curlength+=now.length;

            curArea=curlength*now.height;

            if(curArea>maxArea)

                maxArea=curArea;

        }

        curlength+=e[i].length;

        S.push(Element(curlength,curheight));

    }

    return maxArea;

}

int main()

{

    while(scanf("%d",&n),n!=-){

        for(int i=;i<n;i++)

            scanf("%d%d",&e[i].length,&e[i].height);

        e[n].height=e[n].length=;

        int ans=get_Max();

        printf("%d\n",ans);

    }

    return ;

}