http://acm.pku.edu.cn/JudgeOnline/problem?id=2559
dp題
題目意思就是給你一個柱狀圖。相鄰的幾個柱子包含一個矩形。問這個矩形
面積最大的可能是多少？柱狀圖范圍是1-100000；很大所以O(shè)(n^2)的算法是行不通
的！
假設(shè)當(dāng)前考慮的柱形為i,那么怎么求出以他的高度為大矩形高度的大矩形的面積S
呢？先求出連續(xù)的一段內(nèi)，他左邊的，高度比他大的柱形能到達的最左端left，以及
他右邊的高度比他大的柱形所能到達的最右端right，那么S=(right-left+1)*height[i]；
這樣時間復(fù)雜度為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];//循環(huán)求left
for(i=n;i>=1;i--)
while(height[i]<=height[right[i]+1]) right[i]=right[right[i]+1];//循環(huán)求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")讀數(shù)的，一直RE！改成__int64就AC了！