Posted on 2010-12-07 15:02
小小菜鸟蛋 阅读(374)
评论(0) 编辑 收藏 引用 所属分类:
某蛋的解题报告
http://poj.org/problem?id=2559类似pku2796，求出每个数的区间再计算得出要求的那个最大值。。。
01 #include <cstdio>
02 #include <algorithm>
03 using namespace std;
04
05 const int N = 100000 + 10;
06 long long h[N];
07 int l[N], r[N], stack[N];
08
09 int main()
10 {
11 int n;
12 while (scanf("%d", &n) != EOF && n)
13 {
14 for (int i = 1; i <= n; i++)
15 scanf("%lld", &h[i]);
16 //求左边界
17 int top = 0;
18 stack[top] = 0;
19 h[0] = -1;
20 for (int i = 1; i <= n; i++)
21 {
22 while (h[stack[top]] >= h[i])
23 top--;
24 l[i] = stack[top] + 1;
25 stack[++top] = i;;
26 }
27 //求右边界
28 top = 0;
29 stack[top] = n + 1;
30 h[n+1] = -1;
31 for (int i = n; i >= 1; i--)
32 {
33 while (h[stack[top]] >= h[i])
34 top--;
35 r[i] = stack[top] - 1;
36 stack[++top] = i;
37 }
38 long long ans = -1;
39 for (int i = 1; i <= n; i++)
40 ans = max(ans, (r[i] - l[i] + 1) * h[i]);
41 printf("%lld\n", ans);
42 }
43 }