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

POJ - 2796 Feel Good(经典单调栈)

程序员文章站 2022-03-12 16:33:14
...

传送门


这个题在紫书做过,UVA1619当时看的题解是写的链表,现在学习单调栈需要搞懂这个题的单调栈写法

首先单调栈容易搞晕人的一点是,如果我们求左边/右边第一个小于它的值的位置,那么维护的单调栈从上到下是单调递减的,不能这么想:因为是小于它的所以是单调递增的,应该从“大于等于它的元素出栈,那么单调性就是单调递减的”这点出发
POJ - 2796 Feel Good(经典单调栈)

#include <math.h>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define Vector Point
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const double dinf=1e300;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;

int a[maxn],L[maxn],R[maxn],st[maxn];
ll sum[maxn];

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        sum[i]=sum[i-1]+a[i];
    }
    a[0]=a[n+1]=-inf;
    int head=0;
    st[head++]=0;
    for(int i=1;i<=n;i++){
        while(a[st[head-1]]>=a[i]) head--;
        L[i]=st[head-1]+1;
        st[head++]=i;
    }
    head=0;
    st[head++]=n+1;
    for(int i=n;i>=1;i--){
        while(a[st[head-1]]>=a[i]) head--;
        R[i]=st[head-1]-1;
        st[head++]=i;
    }
    //for(int i=1;i<=n;i++) cout<<L[i]<<" "<<R[i]<<endl;
    ll ans=0;
    int l,r;
    for(int i=1;i<=n;i++){
        ll res=1LL*(sum[R[i]]-sum[L[i]-1])*a[i];
        if(res>=ans){
            ans=res;
            l=L[i],r=R[i];
        }
    }
    printf("%lld\n%d %d\n",ans,l,r);
    return 0;
}
相关标签: 算法