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转一下，然后直接求。。

 1 //STATUS:C++_AC_80MS_1360KB
 2 #include <cmath>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <iostream>
 6 #include <algorithm>
 7 using namespace std;
 8 #define mem(a,b) memset(a,b,sizeof(a))
 9 typedef long long LL;
10 
11 const int N=100010;
12 
13 int l[N],r[N],h[N];
14 int n;
15 
16 int main(){
17  //   freopen("in.txt","r",stdin);
18     int i,j;
19     LL ans;
20     while(~scanf("%d",&n) && n)
21     {
22 
23         for(i=1;i<=n;i++){
24             scanf("%d",&h[i]);
25         }
26         h[0]=-1;
27         for(i=1;i<=n;i++){
28             for(j=i;h[j-1]>=h[i];j=l[j-1]);
29             l[i]=j;
30         }
31         h[n+1]=-1;
32         for(i=n;i>0;i--){
33             for(j=i;h[j+1]>=h[i];j=r[j+1]);
34             r[i]=j;
35         }
36         ans=0;
37         for(i=1;i<=n;i++){
38             ans=max(ans,(LL)h[i]*(r[i]-l[i]+1));
39         }
40 
41         printf("%lld
",ans);
42     }
43     return 0;
44 }