hdu 1506(dp)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1506

大意：求一个最大的区域，则第i个矩形对应的面积是ave[i] = (r[i] - l[i] + 1) * a[i];l[i]表示以它这个高度所能到达的最左边的位置（最左一个高度不小于它的高度的位置），而r[i]表示能到达的最右边的位置（最右一个高度不小于它的高度的位置）。

这道题实际上就是对于任意数x求大于等于x的最左数的下标和最右数的下标;直接进行迭代就行；

#include<iostream>
#include<algorithm>
const int N=110000;
using namespace std;
__int64 h[N],l[N],r[N];

int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        if(n==0)break;
        for(int i=1;i<=n;i++){
            scanf("%I64d",&h[i]);
            l[i]=r[i]=i;
        }
        h[0]=h[n+1]=-1;
        for(int i=1;i<=n;i++){
            while(h[l[i]-1]>=h[i])
                l[i]=l[l[i]-1];
        }
        for(int i=n;i>=1;i--){
            while(h[r[i]+1]>=h[i])
                r[i]=r[r[i]+1];
        }
        __int64 Max=0,ans=0;
        for(int i=1;i<=n;i++){
            ans=(r[i]-l[i]+1)*h[i];
            Max=max(ans,Max);
        }
        printf("%I64d\n",Max);
    }
    return 0;
}