壹、测试题目 ?
使用 [HDU1506]Largest Rectangle in a Histogram 测试。
贰、参考代码 ?
# include <cstdio>
# include <algorithm>
# include <cstring>
# include <vector>
using namespace std;
namespace Elaina {
# define rep(i, l, r) for(int i=(l), i##_end_=(r); i<=i##_end_; ++i)
# define drep(i, l, r) for(int i=(l), i##_end_=(r); i>=i##_end_; --i)
# define fi first
# define se second
# define mp(a, b) make_pair(a, b)
# define Endl putchar(‘\n‘)
# define mmset(a, b) memset(a, b, sizeof (a))
# define mmcpy(a, b) memcpy(a, b, sizeof (a))
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
template <class T> inline T fab(T x) { return x<0? -x: x; }
template <class T> inline void getmin(T& x, const T rhs) { x=min(x, rhs); }
template <class T> inline void getmax(T& x, const T rhs) { x=max(x, rhs); }
template <class T> inline T readin(T x) {
x=0; int f=0; char c;
while((c=getchar())<‘0‘ || ‘9‘<c) if(c==‘-‘) f=1;
for(x=(c^48); ‘0‘<=(c=getchar()) && c<=‘9‘; x=(x<<1)+(x<<3)+(c^48));
return f? -x: x;
}
template <class T> inline void writc(T x, char s=‘\n‘) {
static int fwri_sta[1005], fwri_ed=0;
if(x<0) putchar(‘-‘), x=-x;
do fwri_sta[++fwri_ed]=x%10, x/=10; while(x);
while(putchar(fwri_sta[fwri_ed--]^48), fwri_ed);
putchar(s);
}
} using namespace Elaina;
const int maxn=100000;
int h[maxn+5], n;
int ls[maxn+5], rs[maxn+5], rt;
int stk[maxn+5], ed;
inline void build() {
ed=rt=0; int lst;
rep(i, 1, n) ls[i]=rs[i]=0;
rep(i, 1, n) {
lst=0;
while(ed && h[stk[ed]]>h[i]) lst=stk[ed--];
if(ed) rs[stk[ed]]=i;
else rt=i;
if(lst) ls[i]=lst;
stk[++ed]=i;
}
}
int siz[maxn+5];
void dfs(int u) {
siz[u]=1;
if(ls[u]) dfs(ls[u]);
if(rs[u]) dfs(rs[u]);
siz[u]+=siz[ls[u]]+siz[rs[u]];
}
signed main() {
while(~scanf("%d", &n)) {
if(!n) break;
rep(i, 1, n) h[i]=readin(1);
build(); dfs(rt);
ll ans=0;
rep(i, 1, n) ans=max(ans, 1ll*h[i]*siz[i]);
writc(ans);
}
return 0;
}