BNUOJ-15505 Largest Rectangle in a Histogram DP

时间:2023-03-08 16:13:28
BNUOJ-15505 Largest Rectangle in a Histogram DP

  题目链接:http://www.bnuoj.com/bnuoj/problem_show.php?pid=15505

  每个h[i]维护两个值l[i]和r[i],分别表示大于h[i]的左边最远距离和小于h[i]的右边最远距离,DP转一下,然后直接求。。

 //STATUS:C++_AC_80MS_1360KB
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long LL; const int N=; int l[N],r[N],h[N];
int n; int main(){
// freopen("in.txt","r",stdin);
int i,j;
LL ans;
while(~scanf("%d",&n) && n)
{ for(i=;i<=n;i++){
scanf("%d",&h[i]);
}
h[]=-;
for(i=;i<=n;i++){
for(j=i;h[j-]>=h[i];j=l[j-]);
l[i]=j;
}
h[n+]=-;
for(i=n;i>;i--){
for(j=i;h[j+]>=h[i];j=r[j+]);
r[i]=j;
}
ans=;
for(i=;i<=n;i++){
ans=max(ans,(LL)h[i]*(r[i]-l[i]+));
} printf("%lld\n",ans);
}
return ;
}