HDU 1506 Largest Rectangle in a Histogram

      思路：感覺跟dp有點關系，就放dp類裡了，主要還是模擬思路       對於每一個柱形 K 能得到的最大面積是：（左連續的柱形個數+右連續的柱形個數 ）* High[ K ]   而對於求左右連續個數有點像記憶化搜索   mark：

題意：給定n，後面n個數表示上述柱狀圖的高度（每個柱形底為1）

畫一個矩陣，求面積最大是多少

 

 
#include <iostream>  
#include <string>  
#include <cstring>  
#include <algorithm>  
#include <cstdio>  
#include <cctype>  
#include <queue>  
#include <vector>  
#define inf 1000000000  
#define N 100010  
#define ll __int64  
using namespace std;  
ll a[N],l[N],r[N];//l[i] 表示從 l[i] 到 i 都是連續>=a[i]的數  
  
inline ll Max(ll a,ll b){return a>b?a:b;}  
int main(){  
    int n,i,j,step,temp;  
    while(scanf("%d",&n),n){  
        a[0]=0;  
        for(i=1;i<=n;i++)scanf("%I64d",&a[i]),l[i]=r[i]=i;  
        for(i=1;i<=n;i++)  
            while(l[i]>1 && a[i]<=a[l[i]-1])l[i]=l[l[i]-1];  
  
        for(i=n;i>=1;i--)  
            while(r[i]<n && a[i]<=a[r[i]+1])r[i]=r[r[i]+1];  
  
        ll ans=0;  
        for(i=1;i<=n;i++)  
            ans=Max(ans,(r[i]-l[i]+1)*a[i]);  
        printf("%I64d\n",ans);  
    }  
    return 0;  
}