poj2796 单调栈

题目链接:

题意:

给你一个序列，让你求出一段区间，（在这段区间之内的最小值*这段区间所有元素之和）的最大值……
题解:

http://www.cnblogs.com/ziyi–caolu/archive/2013/06/23/3151556.html
代码:

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <stack>
 5 using namespace std;
 6 typedef long long ll;
 7 #define MS(a) memset(a,0,sizeof(a))
 8 #define MP make_pair
 9 #define PB push_back
10 const int INF = 0x3f3f3f3f;
11 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
12 inline ll read(){
13     ll x=0,f=1;char ch=getchar();
14     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
15     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
16     return x*f;
17 }
18 //////////////////////////////////////////////////////////////////////////
19 const int maxn = 1e5+10;
20 
21 struct node{
22     ll num,pre,nxt;
23     ll pos;
24 };
25 
26 ll a[maxn], sum[maxn];
27 
28 int main(){
29     int n;
30     while(scanf("%d",&n)==1){
31         stack<node> s;
32         sum[0] = 0;
33         for(int i=1; i<=n; i++){
34             a[i] = read();
35             sum[i] = sum[i-1]+a[i];
36         }
37         node k;
38         k.num = a[1]; k.pre = k.nxt = 1; k.pos = 1;
39         s.push(k);
40         ll ans = -1,x,y;
41         for(int i=2; i<=n; i++){
42             node t;
43             t.num = a[i]; t.pre = t.nxt = 1; t.pos = i;
44             while(!s.empty() && t.num<=s.top().num){
45                 node tt = s.top();
46                 s.pop();
47                 if(!s.empty())
48                     s.top().nxt += tt.nxt;
49                 t.pre += tt.pre;
50                 ll tmp = tt.num*(sum[tt.pos+tt.nxt-1]-sum[tt.pos-tt.pre]);
51                 // cout << tt.pos << " " << tt.pre << " " << tt.nxt << " " << tmp << endl;
52                 if(ans < tmp){
53                     ans = tmp;
54                     x = tt.pos-tt.pre+1;
55                     y = tt.pos+tt.nxt-1;
56                 }
57             }
58             s.push(t);
59         }
60 
61         while(!s.empty()){
62             node tt = s.top();
63             s.pop();
64             if(!s.empty())
65                 s.top().nxt += tt.nxt;
66 
67             ll tmp = tt.num*(sum[tt.pos+tt.nxt-1]-sum[tt.pos-tt.pre]);
68             if(ans < tmp){
69                 ans = tmp;
70                 x = tt.pos-tt.pre+1;
71                 y = tt.pos+tt.nxt-1;
72             }
73         }
74 
75         cout << ans << endl << x << " " << y << endl;
76     }
77 
78     return 0;
79 }
80 // http://www.cnblogs.com/ziyi--caolu/archive/2013/06/23/3151556.html