Largest Rectangle in a Histogram [여름 훈련 Q 문제][DP][귀속]

이때 AK까지 한 문제가 모자랐고 공교롭게도 마침 피를 흘린 문제를 써야 했다.
A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles: 
 
Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.
InputThe input contains several test cases. Each test case describes a histogram and starts with an integer n, denoting the number of rectangles it is composed of. You may assume that 1 <= n <= 100000. Then follow n integers h1, ..., hn, where 0 <= hi <= 1000000000. These numbers denote the heights of the rectangles of the histogram in left-to-right order. The width of each rectangle is 1. A zero follows the input for the last test case.OutputFor each test case output on a single line the area of the largest rectangle in the specified histogram. Remember that this rectangle must be aligned at the common base line.Sample Input

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

Sample Output

8
4000

사고방식: 이 문제의 뜻은 우리가 그림에서 구성할 수 있는 최대 직사각형 면적을 구하는 것이다. 우리는 직사각형의 면적이 장승폭이 아니라는 것을 알고 있다. 우리가 요구하는 점이 구성할 수 있는 최대 면적에 대해 그 좌우가 그것보다 큰 극한까지 갈 수 있도록 요구할 뿐이다.그러나 여기서 우리는 몇 가지 조작이 필요하다. 즉, 이 문제가 T의 주요 조작을 방지하는 것이다.
중점: 우리는 모든 점에 대해 그의 좌우 극한을 요구한 다음에 면적을 계산하는 조작을 한다. 그러면 나는 이 점의 왼쪽 극한을 구하는 방식을 통해 같은 이치로 오른쪽 극한을 구할 수 있다.
왼쪽 극한 L의 구법에 대해 우리는 첫 번째 수에서 n(두 개의 단점)까지 구했다. 1과 같은 것은 왼쪽 극한이 없다. 그러면 그의 왼쪽 극한은 바로 그 자체이다. 그리고 2를 보면 우리는 그것을 1과 비교해서 그의 왼쪽 극한 L이 그 자체인지 1인지를 결정한다.다음에 i번째 점에 대해 우리는 그의 왼쪽 극한 L을 구하고 먼저 그것과 왼쪽의 그 수를 비교한다. 만약에 그것보다 크거나 같으면 우리는 먼저 i의 왼쪽 극한을 i-1의 왼쪽 극한 L[i-1]까지 미룰 수 있다. 그러면 우리는 지금 판결을 끝내야 하는가?이것은 L[i-1]-1 이 점에 달려 있다. 왜?왜냐하면 i점은 i-1점과 같은 높이보다 작기 때문에 i-1점의 왼쪽 한계는 i에게 계승될 수 있지만 i-1점이 i보다 높다면 이것은'충분한 불필요'조건이다. 우리는 이때 L[i-1]-1점의 높이가 i보다 높은지 확인할 수 없기 때문에 일일이 판단하면 우리는 유용한 공식을 내놓을 수 있다.
            while(l[i]>0&&a[l[i]-1]>=a[i])
            {
                l[i]=l[l[i]-1];
            }
같은 도리로 우리는 유사한 방법으로 각 점의 오른쪽 극한을 구할 수 있다
전체 코드:

#include 
#include 
#include 
using namespace std;
typedef long long ll;
int n;
int a[100005];
int l[100005],r[100005];        //                      
int main()
{
    while(scanf("%d",&n)&&n)
    {
        ll ans=0;
        memset(a, 0, sizeof(a));
        for(int i=0; i0&&a[l[i]-1]>=a[i])
            {
                l[i]=l[l[i]-1];
            }
        }
        for(int i=n-1; i>=0; i--)
        {
            while(r[i]=a[i])
            {
                r[i]=r[r[i]+1];
            }
        }
        for(int i=0; ians)
            {
                ans=s;
            }
        }
        printf("%lld
",ans);
    }
    return 0;
}