poj 2796 Feel Good (前缀和,单调栈)

Posted by 111qqz on Wednesday, August 3, 2016

TOC

poj 2796

题意:给出一个人n(1E5)天的情绪值(0..1E6),一段时间的value的定义是这段时间的情绪之和*这段时间情绪的最小值。

现在求value的最大值,并且输出得到这个最大值的区间。

思路:单调栈。 考虑把每一天作为最小值的时候能向左向由延伸的最远的点的下标,两个方向各做一次单调栈来预处理。和的haunted前缀和搞下。。

然后最后想着了LL,但是读入的时候前缀和的那里忘了LL wa了一发。。。2A

/* ***********************************************
Author :111qqz
Created Time :2016年08月03日 星期三 19时14分42秒
File Name :code/poj/2796.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E5+7;
int n;
int a[N];
LL sum[N];
int l[N],r[N];
stack<int>stk;
int main()
{
    #ifndef  ONLINE_JUDGE 
    freopen("code/in.txt","r",stdin);
  #endif

    scanf("%d",&n);
    sum[0] = 0 ;
    for ( int i = 1 ; i <= n ; i++) scanf("%d",&a[i]),sum[i] = sum[i-1] + 1LL*a[i];
	
    a[0]=a[n+1]=-1; //哨兵
	
    int x;
    stk.push(0);
    for ( int i = 1 ; i <= n ; i++)
    {
        for (x=stk.top(); a[x]>=a[i] ; x=stk.top()) stk.pop();
        l[i] = x + 1;
        stk.push(i);
    }
	
    while (!stk.empty()) stk.pop();
    stk.push(n+1);
    for ( int i = n ; i >=1 ; i--)
    {
        for (x=stk.top() ; a[x]>=a[i] ; x=stk.top()) stk.pop();
        r[i] = x-1;
        stk.push(i);
    }
    LL ans = -1LL;
    int L,R;
    for ( int i = 1 ; i <= n ; i++)
    {
        LL cur = 1LL*(sum[r[i]]-sum[l[i]-1])*a[i];
        if (cur>ans)
        {
        ans = cur;
        L = l[i];
        R = r[i];
        }
    }
    printf("%lld\n%d %d\n",ans,L,R);


  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付