POJ 2796[UVA 1619] Feel Good

Feel Good

Time Limit: 3000MS		Memory Limit: 65536K
Total Submissions: 16786		Accepted: 4627
Case Time Limit: 1000MS		Special Judge

Description

Bill is developing a new mathematical theory for human emotions. His recent investigations are dedicated to studying how good or bad days influent people's memories about some period of life. 

A new idea Bill has recently developed assigns a non-negative integer value to each day of human life. 

Bill calls this value the emotional value of the day. The greater the emotional value is, the better the daywas. Bill suggests that the value of some period of human life is proportional to the sum of the emotional values of the days in the given period, multiplied by the smallest emotional value of the day in it. This schema reflects that good on average period can be greatly spoiled by one very bad day. 

Now Bill is planning to investigate his own life and find the period of his life that had the greatest value. Help him to do so.

Input

The first line of the input contains n - the number of days of Bill's life he is planning to investigate(1 <= n <= 100 000). The rest of the file contains n integer numbers a1, a2, ... an ranging from 0 to 10⁶ - the emotional values of the days. Numbers are separated by spaces and/or line breaks.

Output

Print the greatest value of some period of Bill's life in the first line. And on the second line print two numbers l and r such that the period from l-th to r-th day of Bill's life(inclusive) has the greatest possible value. If there are multiple periods with the greatest possible value,then print any one of them.

Sample Input

6
3 1 6 4 5 2

Sample Output

60
3 5

Source

Northeastern Europe 2005

 

题目链接

 

题意 

求任意一个区间，它的区间和乘上区间内最小值后的数值是最大的。

 

分析 

先维护前缀和，再求出以每个元素为最小值的区间范围，然后计算取最大值即可。求以每个元素为最小值的区间范围可以使用单调栈来实现。每次入栈，都与栈顶元素比较，我们要维护一个从栈底到栈顶，从小到大的栈，若栈顶元素小于当前元素，则入栈；否则，把栈里小于当前元素的项一一出栈并计算对应的值，因为此时相对于已经发现了第一个比栈里某些元素小的值，所以那些项不可作为新区间的最小值了，也就是找到作为最小值的右边界了，同时，按照栈里的顺序就知道了左边界，这样以每个元素为最小值的区间范围就求出来了，答案便是所有的最大值了。

另外，uva上这题很坑啊，死活都是wa，最后用了一种比较巧妙的方法，即暴力作区间的标记。建议在poj上提交代码

 

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include <queue>
#include <vector>
#include<bitset>
#include<map>
using namespace std;
typedef long long LL;
const int maxn = 1e5+5;
const int mod = 772002+233;
typedef pair<int,int> pii;
#define X first
#define Y second
#define pb push_back
#define mp make_pair
#define ms(a,b) memset(a,b,sizeof(a))
const int inf = 0x3f3f3f3f;
#define lson l,m,2*rt
#define rson m+1,r,2*rt+1
int a[maxn],sta[maxn];
LL sum[maxn];
int lef[maxn];
int main(){
//    freopen("in.txt","r",stdin);
    int n;
    while(~scanf("%d",&n)){
        ms(sum,0);

        int top=-1;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            sum[i]=sum[i-1]+a[i];
        }
        a[n+1]=-1;
        LL ans=-1;
        int L,R;
        for(int i=1;i<=n+1;i++){
//            cout<<a[i]<<endl;
            if(a[i]>sta[top] || top==-1){
                sta[++top]=a[i];
                lef[top]=i;
//                printf("%d,(%d,%d)
",a[i],i,i);
            }else if(a[i]<sta[top]){
                int ll;
                while(a[i]<sta[top]&&top>=0){
                    ll=lef[top];
                    LL res=(sum[i-1]-sum[lef[top]-1])*sta[top]*1LL;
                    if(res > ans){
                        ans=res;
                        L=lef[top],R=i-1;
                    }
                    top--;
                }
                sta[++top]=a[i];
                lef[top]=ll;
//                printf("%d,(%d,%d)
",a[i],ll,i);
            }
        }
        cout<<ans<<endl;
        cout<<L<<" "<<R<<endl;
    }
    return 0;
}

uva上能通过的代码

#include<cstdio>
#include<cstring>
#define maxn 1000010
long long sum[maxn];
int num[maxn], l[maxn], r[maxn], n;
void init() {
    sum[0] = 0;
    memset(num,-1,sizeof(num));
    for(int i = 1; i <= n; i++) {
        scanf("%d", &num[i]);
        sum[i] = sum[i-1] + num[i];
        l[i] = i;
        r[i] = i;
    }

    for(int i = 1; i <= n; i++) {
        while(num[l[i] - 1] >= num[i])
            l[i] = l[l[i] - 1];
    }
    for(int i = n; i >= 1; i--) {
        while(num[r[i] + 1] >= num[i])
            r[i] = r[r[i] + 1];
    }
}

void solve() {
    long long Max = 0;
    int ll = 1, rr = 1;
    long long s;
    for(int i = 1; i <= n; i++) {
        s = num[i] * (sum[r[i]] - sum[l[i] - 1]);
        if(s > Max || (s == Max && rr - ll > r[i] - l[i])) {
            Max = s;
            ll = l[i];
            rr = r[i];
        }
    }
    printf("%lld
%d %d
", Max, ll, rr);
}

int main() {
    int cas = 0;
    while(scanf("%d", &n) != EOF) {
        if(cas)
            printf("
");
        cas++;
        init();
        solve();
    }
    return 0;
}