poj 2796 单调栈(秒懂)
程序员文章站
2022-06-04 16:08:37
...
poj- 2796
单调栈维护高度, 前缀和也要维护高度,这题可以看作求max(a[i] * (sum[r[i]] - sum[l[i]])), 其中l[i]和r[i],分别表示第i个数的左边、右边比他小的第一个数的下标:
我知道你们只看这个
#pragma G++ optimize(2)
#pragma GCC optimize(2)
#define DEBUG
#include<iostream>
#include<algorithm>
#include<stack>
#include<vector>
#include<iostream>
#include<climits>
#include<queue>
#include<cassert>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstdio>
#include<cstring>
#define _rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define _rev(i, a, b) for(int i = (a); i >= (b); --i)
#define _for(i, a, b) for(int i = (a); i <(b); ++i)
#define _rof(i, a, b) for(int i = (a); i >(b); --i)
#define maxn 100009
#define maxm 109
#define ll long long
#define met(a,b) memset((a),(b), sizeof(a))
#define db double
#define eps 1e-8
using namespace std;
int n;
int le = 1, ri = 1;
ll h[maxn], r[maxn], sum[maxn], s[maxn], l[maxn];
int main()
{
//freopen("C:\\Users\\Jason.Z\\Desktop\\out.txt", "w", stdout);
while (~scanf("%d", &n)) {
_rep(i, 1, n) {
scanf("%lld", &h[i]);
sum[i] = h[i] + sum[i - 1];
}
int top = 0;
_rep(i, 1, n) {
while (top && h[s[top]] >= h[i]) top--;//栈单增,遇到比我高的就pop
l[i] = top ? s[top] + 1 : 1;//若栈空(没有数比我小),则l[i] = 1, 反之则取比我小的这个数的前一个
s[++top] = i;
}
top = 0;
_rev(i, n, 1) {
while (top && h[s[top]] >= h[i])top--;
r[i] = top ? s[top] - 1 : n;//若栈空(右边没有比我小的数)则,取到最右n,反之则取比我小的这个数的前一个
s[++top] = i;
}
ll out = 0;
le = 1, ri = 1;
_rep(i, 1, n) {
ll ans = h[i] * (sum[r[i]] - sum[l[i] - 1]);//区间包括左端点l[i],即sum[r[i]] - sum[l[i] - 1]
if (ans > out) {
out = ans;
le = l[i];
ri = r[i];
}
}
cout << out << endl;
cout << le << " " << ri << endl << endl;
}
}
若有错谬之处欢迎指正
下一篇: ROS学习1----安装和配置