infinity

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  36 随笔 :: 0 文章 :: 25 评论 :: 0 Trackbacks
http://acm.pku.edu.cn/JudgeOnline/problem?id=2559
dp题

题目意思就是给你一个柱状图。相邻的几个柱子包含一个矩形。问这个矩形

面积最大的可能是多少?柱状图范围是1-100000;很大所以O(n^2)的算法是行不通

的!

假设当前考虑的柱形为i,那么怎么求出以他的高度为大矩形高度的大矩形的面积S
呢?先求出连续的一段内,他左边的,高度比他大的柱形能到达的最左端left,以及
他右边的高度比他大的柱形所能到达的最右端right,那么S=(right-left+1)*height[i];
这样时间复杂度为O(n);所iguanjian是求出每个矩形的left,right!!

Source Code

Problem: 2559
User: lovecanon
Memory: 2552K
Time: 188MS
Language: C++
Result: Accepted

#include<stdio.h>
__int64 height[
100001],right[100001],left[100001],max,tmp,i,n;
int main(){
    
while(scanf("%I64d",&n),n!=0){
        
for(i=1;i<=n;i++) {
            scanf(
"%I64d",&height[i]);
            left[i]
=right[i]=i;
        }
        height[
0]=height[n+1]=-1;
        
for(i=1;i<=n;i++)
            
while(height[i]<=height[left[i]-1]) left[i]=left[left[i]-1];//循环求left
        
for(i=n;i>=1;i--)
            
while(height[i]<=height[right[i]+1]) right[i]=right[right[i]+1];//循环求right
        
for(max=0,i=1;i<=n;i++)
            
if((tmp=(right[i]-left[i]+1)*height[i])>max) max=tmp;//找最大值
        printf(
"%I64d\n",max);
    }
    
return 0;
}

还有就是我刚开始用的long long +scanf("%lld")读数的,一直RE!改成__int64就AC了!

posted on 2008-11-02 00:22 infinity 阅读(606) 评论(0)  编辑 收藏 引用 所属分类: acm

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理