先上题目:
Time Limit: 2000/1000 MS
(Java/Others) Memory Limit: 65536/32768 K
(Java/Others)
Total Submission(s): 9826 Accepted
Submission(s): 2717
1 #include <cstdio> 2 #include <cstring> 3 #define max(x,y) (x > y ? x : y) 4 #define MAX 100002 5 #define LL long long 6 using namespace std; 7 8 LL h[MAX]; 9 int l[MAX],r[MAX]; 10 11 int main() 12 { 13 int n; 14 LL maxn; 15 //freopen("data.txt","r",stdin); 16 while(scanf("%d",&n),n){ 17 for(int i=1;i<=n;i++){ 18 scanf("%I64d",&h[i]); 19 l[i]=r[i]=i; 20 } 21 h[0]=h[n+1]=-1; 22 for(int i=2;i<=n;i++){ 23 while(h[i]<=h[l[i]-1]){ 24 l[i]=l[l[i]-1]; 25 } 26 } 27 28 for(int i=n-1;i>0;i--){ 29 while(h[i]<=h[r[i]+1]){ 30 r[i]=r[r[i]+1]; 31 } 32 } 33 maxn=0; 34 for(int i=1;i<=n;i++){ 35 LL s=h[i]*(r[i]-l[i]+1); 36 maxn=max(s,maxn); 37 } 38 printf("%I64d\n",maxn); 39 } 40 return 0; 41 }
HDU - 1506 - Largest Rectangle in a Histogram,布布扣,bubuko.com
HDU - 1506 - Largest Rectangle in a Histogram
原文:http://www.cnblogs.com/sineatos/p/3600351.html