POJ 2559水問題
クリックしてリンクを開く
いくつかの連続する高さを与えて、最大で形成できる長方形を求めます.
思考:高さごとに求めて、この高さでカバーできる左右の位置をL[i]とR[i]で保存し、相乗後に最大値を出力すればいいです.
いくつかの連続する高さを与えて、最大で形成できる長方形を求めます.
思考:高さごとに求めて、この高さでカバーできる左右の位置をL[i]とR[i]で保存し、相乗後に最大値を出力すればいいです.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=100010;
int num[maxn],H[maxn],L[maxn],R[maxn];
int main(){
int n;
while(scanf("%d",&n)!=-1){
if(n==0) break;
memset(num,0,sizeof(num));
for(int i=1;i<=n;i++) scanf("%d",&H[i]);
int t=0;
for(int i=1;i<=n;i++){
while(t>0&&H[num[t-1]]>=H[i]) t--;
if(t==0) L[i]=0;
else L[i]=num[t-1];
num[t++]=i;
}
t=0;
for(int i=n;i>=1;i--){
while(t>0&&H[num[t-1]]>=H[i]) t--;
if(t==0) R[i]=n;
else R[i]=num[t-1]-1;
num[t++]=i;
}
__int64 ans=0;
for(int i=1;i<=n;i++){
ans=max(ans,(__int64)H[i]*(R[i]-L[i]));
}
printf("%I64d
",ans);
}
return 0;
}