526互联

SPOJ1805 HISTOGRA - Largest Rectangle in a Histogram 题解

发布时间 2023-11-13 22:59:24作者: Martian148

Link

SPOJ1805 HISTOGRA - Largest Rectangle in a Histogram

Question

在一条水平线上有 \(n\) 个高为 \(a_i\) 的矩形，求包含于这些矩形的最大子矩形面积。

Solution

我们定义 \(L_i\) 表示有 \(a_i\) 这个高度的一根悬线，往左最多能平移到什么位置

初始化显然，\(a_i=i\)

考虑转移

  • 如果当前 \(l_i=1\) 则已经扩展到了
  • 如果当前 \(a_i > a_{l_i-1}\) 则从当前悬线不能平移到 \(L_i-1\)
  • 如果当前 \(a_i \le a_{l_i-1}\) 则当前悬线能平移到 \(Li-1\) 往左边平移到的最远的地方

同样的构造一个 \(R_i\) 就好了

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=100005;
int N,a[maxn];
int L[maxn],R[maxn];
int main(){
    freopen("SP1805.in","r",stdin);
    while(scanf("%d",&N)!=EOF&&N){
        LL ans=0;
        for(int i=1;i<=N;i++) scanf("%d",&a[i]),L[i]=R[i]=i;
        for(int i=1;i<=N;i++) 
            while(L[i]>1&&a[i]<=a[L[i]-1]) L[i]=L[L[i]-1];
        for(int i=N;i;i--)
            while(R[i]<N&&a[i]<=a[R[i]+1]) R[i]=R[R[i]+1];
        for(int i=1;i<=N;i++)
            ans=max(ans,(LL)(R[i]-L[i]+1)*a[i]);
        printf("%lld\n",ans);
    }
    return 0;
}