poj 2769 感觉♂良好（单调栈）

比尔正在研发一种关于人类情感的新数学理论。他最近致力于研究一个日子的好坏，如何影响人们对某个时期的回忆。比尔为人的一天赋予了一个正整数值。比尔称这个值为当天的情感价值。情感价值越大，日子过的越好。比尔认为，某个时期人的情感，与某一时期的情感价值总和，乘以这一阶段的最小情感价值成正比。这个想法表示，一段时期的好心情可以被糟糕的一天破坏。现在比尔正在审视自己的生活，并希望找到最有价值的人生阶段。请你帮帮他。由于他过度♂劳累，他的生命天数n<=10000。

这道题的思路和矩阵那道题一样，都是假定某个数为最小值，向左/向右扩展。求向左/向右最近最小值就是用单调栈。思路不详细说了。

然而我发现了单调栈的两个要素：维护与求最值。似乎能用单调栈解的题目，都必须满足，能在维护单调栈的同时，均摊O(1)求出最优解。所以能用单调栈解的题目都有这种很特殊的性质。如果不确定是不是玄学解法，应该证一证。

#include <cstdio>

using namespace std;

typedef long long LL;

const int maxn=1e5+5, INF=1e9;

struct stack{

    int t, a[maxn];

    void push(int x){ a[++t]=x; }

    void pop(){ if (--t==-1) ++t; }

    int top(){ return a[t]; }

    void RESET(){ t=0; }

}s;

LL ans, sum[maxn];

int n, ans2, a[maxn];

int left[maxn], right[maxn];

int main(){

    while (~scanf("%d", &n)){  //可能此处bug

        ans=ans2=0;

        for (int i=1; i<=n; ++i){

            scanf("%d", &a[i]);

            sum[i]=sum[i-1]+a[i];

        }

        a[0]=a[n+1]=-INF; s.push(0);

        for (int i=1; i<=n; ++i){

            while (a[i]<=a[s.top()]) s.pop();

            left[i]=s.top(); s.push(i);

        }

        s.RESET(); s.push(n+1);

        for (int i=n; i>0; --i){

            while (a[i]<=a[s.top()]) s.pop();

            right[i]=s.top(); s.push(i);

        } LL v;

        for (int i=1; i<=n; ++i){

            v=a[i]*(sum[right[i]-1]-sum[left[i]]);

            if (v>=ans){ ans=v; ans2=i; }  //可能此处bug

        }

        printf("%lld\n%d %d\n", ans, left[ans2]+1, right[ans2]-1);

        s.RESET();

    }

    return 0;

}

巴特西

poj 2769 感觉♂良好（单调栈）

poj 2769 感觉♂良好（单调栈）

最新文章

热门文章

巴特西

poj 2769 感觉♂良好 （单调栈）

poj 2769 感觉♂良好 （单调栈）

最新文章

热门文章

poj 2769 感觉♂良好（单调栈）

poj 2769 感觉♂良好（单调栈）