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了！