【題目大意】給定n個連續(xù)的長度為1的矩形的高度h（1<=n<=100000，0<=hi<=1000000000），問你其中能構成的最大矩形的面積是多少。【思路】很顯然，用DP。但關鍵是怎樣表示狀態(tài)，一開始想用一個二維數組min[][]表示從i～j的最小高度，面積就等于min[i][j]*(j-i+1)。但很不幸，根據題目給定的n的范圍，這個二維數組根本無法創(chuàng)建。:( 后來從論壇上得到提示，因為對于圖中的某個面積最大的矩形，必然有一個最低的高度h[k]，即矩形的高等于h[k]，以第k塊矩形的高度，最左邊可以到達這個矩形的左邊，最右邊可以到達這個矩形的右邊。所以，可以以每塊矩形進行擴展，求出最左邊和最右邊（即兩邊的高度都大于等于這塊的高度），得出面積s[i]，這樣就可求出最大的s[i]了。
  PKU 2559
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
#define maxn 100000+5
__int64 h[maxn];
int l[maxn],r[maxn];
int n;
void solve()
{
h[0]=h[n+1]=-1;
for(int i=1;i<=n;i++)
l[i]=r[i]=i;
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 ans=0;
for(int i=1;i<=n;i++)
ans=max(h[i]*(r[i]-l[i]+1),ans);
printf("%I64d\n",ans);
}
int main()
{
while(scanf("%d",&n)!=EOF && n)
{
for(int i=1;i<=n;i++)
scanf("%I64d",&h[i]);
solve();
}
}
|