F - Feel Good Gym - 101334F 经典思维（前缀和）

本文主要是介绍F - Feel Good Gym - 101334F 经典思维（前缀和），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

给出正整数的数组，让你求出此数组某一个区间的和乘以区间内的最小值

题解：

求出前缀和，然后求出每一个数比这个数小的左右端点

这里注意一个优化：就可以跳着走，当一个数比他大的时候，然后就可以跳到比他大的数的端点去

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;#define LL long long
#define MAXN 100005
int L[MAXN],R[MAXN];
int a[MAXN];
LL sum[MAXN];int main()
{int n;//freopen("in.txt","r",stdin);freopen("feelgood.in","r",stdin);freopen("feelgood.out","w",stdout);while(scanf("%d",&n)!=EOF){sum[0]=0;for(int i=1;i<=n;i++){scanf("%d",&a[i]);sum[i]=sum[i-1]+a[i];}L[0]=1;R[n]=n+1;int i,j;for(i=2;i<=n;i++){for(j=i-1;j>=1;){if(a[j]<a[i]){ L[i]=j;break;}else j=L[j];}}for(i=n-1;i>=1;i--){for(j=i+1;j<=n;){if(a[j]<a[i]){ R[i]=j;break;}else j=R[j];}if(j>n)R[i]=n+1;}LL ans=-1,temp;int l,r;for(int i=1;i<=n;i++){temp=a[i]*(sum[R[i]-1]-sum[L[i]]);if(ans<temp)ans=temp,l=L[i]+1,r=R[i]-1;}printf("%lld\n%d %d\n",ans,l,r);}return 0;
}

这篇关于F - Feel Good Gym - 101334F 经典思维（前缀和）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---