【题目大意】给定n个连续的长度为1的矩形的高度h（1<=n<=100000，0<=hi<=1000000000），问你其中能构成的最大矩形的面积是多少。【思路】很显然，用DP。但关键是怎样表示状态，一开始想用一个二维数组min[][]表示从i～j的最小高度，面积就等于min[i][j]*(j-i+1)。但很不幸，根据题目给定的n的范围，这个二维数组根本无法创建。:( 后来从论坛上得到提示，因为对于图中的某个面积最大的矩形，必然有一个最低的高度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();
}
}
|