Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 9550 Accepted Submission(s): 2633
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.|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 |
#include<iostream>#include<cstring>#include<cstdio>using
namespace std;int l[100010],r[100010];int
a[100010];int main(){ int
t,i; long
long m,max; while(scanf("%d",&t)!=EOF&&t!=0) { max=0; memset(a,0,sizeof(a)); for(i=1;i<=t;i++) scanf("%d",&a[i]); for(i=1;i<=t;i++) { l[i]=i; while(l[i]>1&&a[l[i]-1]>=a[i]) l[i]=l[l[i]-1]; } for(i=t;i>=1;i--) { r[i]=i; while(r[i]<t&&a[r[i]+1]>=a[i]) r[i]=r[r[i]+1]; } for(i=1;i<=t;i++) { m=(long
long)(r[i]-l[i]+1)*a[i]; if(max<m) max=m; } cout<<max<<endl; } return
0;}// 4 1000000000 1000000000 1000000000 1000000000 |
HDU-1506 Largest Rectangle in a Histogram
原文：http://www.cnblogs.com/cancangood/p/3562498.html