洛谷P2422 良好的感觉

题目描述

kkk做了一个人体感觉分析器。每一天，人都有一个感受值Ai，Ai越大，表示人感觉越舒适。在一段时间[i, j]内，人的舒适程度定义为[i, j]中最不舒服的那一天的感受值 * [i, j]中每一天感受值的和。现在给出kkk在连续N天中的感受值，请问，在哪一段时间，kkk感觉最舒适？

输入输出格式

输入格式：

第一行为N，代表数据记录的天数

第二行N个整数，代表每一天的感受值

输出格式：

一行，表示在最舒适的一段时间中的感受值。

输入输出样例

输入样例#1：

6
3 1 6 4 5 2

输出样例#1：

说明

样例解释：

kkk最开心的一段时间是第3天到第5天，开心值：(6+4+5)*4=60

对于30%的数据，1<=N<=100

对于70%的数据，1<=N<=2000

对于100%的数据，1<=N<=100000，1<=感受值<=1000000

/*
    st表预处理区间最小值，前缀和处理区间和，总复杂度大约O(n^2)
*/
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define maxn 100010
int n,a[maxn],mn[maxn][21],sum[maxn];
long long ans;
int find(int l,int r){
    int k=0;
    while(1<<(k+1)<=(r-l+1))k++;
    int Ans=min(mn[l][k],mn[r-(1<<k)+1][k]);
    return Ans;
}
int main(){
    //freopen("Cola.txt","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        sum[i]=sum[i-1]+a[i];
        mn[i][0]=a[i];
    }
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++){
            long long now=1LL*(sum[j]-sum[i-1])*find(i,j);
            ans=max(ans,now);
        }
    cout<<ans;
}

70分暴力

/*
    换一个角度看问题，如果我们穷举一个最小值a[i],然后往左右扩展，显然是对的，复杂度 O(n^2)。所以我们要优化一下这个扩展过程。首先扩展这个过程的原则就是所有加入这个区间的数都必须小于选定的最小值 a[i]，那么我们可以把扩展过程换一个叙述方法，就是对于每个数我们分别往左右找到第一个比 a[i]小的数，编号分别记成 l[i]、r[i]，则答案就是 sum(l[i]+1,r[i]-1)*×a[i]。
    
    那么这两个数怎么求呢？可以正着跑一遍单调栈，再翻着跑一遍单调栈，再用前缀和搞一下就行了。时间复杂度 O(n)O(n)。
*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 100010
long long st[maxn],sum[maxn],l[maxn],r[maxn];
int a[maxn],n;
long long ans;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        sum[i]=sum[i-1]+a[i];
    }
    int top=0;
    for(int i=1;i<=n;i++){
        while(top&&a[st[top]]>a[i]){r[st[top]]=i;top--;}
        st[++top]=i;
    }
    top=0;
    for(int i=n;i>=1;i--){
        while(top&&a[st[top]]>a[i]){l[st[top]]=i;top--;}
        st[++top]=i;
    }
    for(int i=1;i<=n;i++){
        long long now=1LL*a[i]*(sum[r[i]-1]-sum[l[i]]);
        ans=max(ans,now);
    }
    cout<<ans;
}

100分单调栈