欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

poj 2796 单调栈(秒懂)

程序员文章站 2022-06-04 16:08:37
...

poj- 2796

poj 2796 单调栈(秒懂)
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;
 }
}

若有错谬之处欢迎指正

poj 2796 单调栈(秒懂)