QuXiao

每天进步一点点!

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  50 随笔 :: 0 文章 :: 27 评论 :: 0 Trackbacks
题目大意:
    给定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]了。

代码:

#include <cstdio>

const int MAX = 100005;
__int64 h[MAX];
__int64 left[MAX], right[MAX];        //left[i] = j表示第i个矩形以它的高度到达最左边的下标
int n;

bool Input ()
{
    scanf("%d", &n);
    if ( n == 0 )
        return false;
    int i;
    for (i=1; i<=n; i++)
        scanf("%I64d", &h[i]);
    h[0] = h[n+1] = -1;
    return true;
}

void Solve ()
{
    int i;
    __int64 temp, max;
    for (i=1; i<=n; i++)
    {
        left[i] = right[i] = i;
    }

    for (i=1; i<=n; i++)
    {
        while ( h[left[i]-1] >= h[i] )
            left[i] = left[left[i]-1];
    }
    for (i=n; i>0; i--)
    {
        while ( h[right[i]+1] >= h[i] )
            right[i] = right[right[i]+1];
    }

    max = 0;
    for (i=1; i<=n; i++)
    {
        temp = h[i] * (right[i] - left[i] + 1);
        if ( temp > max )
            max = temp;
    }

    printf("%I64d\n", max);
}

int main ()
{
    while ( Input() )
    {
        Solve();
    }

    return 0;
}


posted on 2008-02-01 19:34 quxiao 阅读(1805) 评论(0)  编辑 收藏 引用 所属分类: ACM

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理