P2659 美丽的序列
思想是将序列上的所有数放入栈中延后处理，使得栈中呈现出单调递增性。每个栈里的元素维护一个 $w$ 表示在它自己和前面有多少的元素小于等于它，当有一个新的元素添加进来的时候，如果比当前栈顶还大，那么直接放入栈，显然 $w = 1$ ；否则不断从栈找到之前的，将这些 $w$ 累加起来就是以这个元素为最小值的区间长度，同时累加的 $w$ 加上自己就是这个元素的 $w$。
查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 2e6 + 10;
struct Node
{
int v, w;
} stk[N];
int top;
int n, h[N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &h[i]);
h[n + 1] = 0;
top = 0;
LL res = 0;
for (int i = 1; i <= n + 1; i++)
{
if (h[i] > stk[top].v && top)
{
stk[++top].v = h[i];
stk[top].w = 1;
}
else
{
int w = 0;
while (stk[top].v > h[i])
{
w += stk[top].w;
res = max(res, (LL)w * stk[top].v);
top--;
}
stk[++top].v = h[i];
stk[top].w = w + 1;
}
}
printf("%lld\n", res);
return 0;
}
|