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

2016-08-03 · 1 min read · 前缀和 单调栈

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
************************************************ */

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <stack>
 8#include <set>
 9#include <map>
10#include <string>
11#include <cmath>
12#include <cstdlib>
13#include <ctime>
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19typedef long long LL;
20#define pi pair < int ,int >
21#define MP make_pair

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

1	scanf("%d",&n);
2	sum[0] = 0 ;
3	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; //哨兵

1	int x;
2	stk.push(0);
3	for ( int i = 1 ; i <= n ; i++)
4	{
5	    for (x=stk.top(); a[x]>=a[i] ; x=stk.top()) stk.pop();
6	    l[i] = x + 1;
7	    stk.push(i);
8	}

 1	while (!stk.empty()) stk.pop();
 2	stk.push(n+1);
 3	for ( int i = n ; i >=1 ; i--)
 4	{
 5	    for (x=stk.top() ; a[x]>=a[i] ; x=stk.top()) stk.pop();
 6	    r[i] = x-1;
 7	    stk.push(i);
 8	}
 9	LL ans = -1LL;
10	int L,R;
11	for ( int i = 1 ; i <= n ; i++)
12	{
13	    LL cur = 1LL*(sum[r[i]]-sum[l[i]-1])*a[i];
14	    if (cur>ans)
15	    {
16		ans = cur;
17		L = l[i];
18		R = r[i];
19	    }
20	}
21	printf("%lld\n%d %d\n",ans,L,R);

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}