洛谷 P2659 美丽的序列 解题报告

序列 解题报告"/>

洛谷 P2659 美丽的序列 解题报告

P2659 美丽的序列

题目背景

GD是一个热衷于寻求美好事物的人，一天他拿到了一个美丽的序列。

题目描述

为了研究这个序列的美丽程度，GD定义了一个序列的“美丽度”和“美丽系数”：对于这个序列的任意一个区间\([l,r]\)，这个区间的“美丽度”就是这个区间的长度与这个区间的最小值的乘积，而整个序列的“美丽系数”就是它的所有区间的“美丽度”的最大值。现在GD想要你帮忙计算这个序列的“美丽系数”。

输入输出格式

输入格式：

第一行一个整数n，代表序列中的元素个数。 第二行n个整数a1、a2„an，描述这个序列。

输出格式：

一行一个整数，代表这个序列的“美丽系数”。

说明：

对于100%的数据，\(1<=n<=2000000，0<=ai<=2000000\)

思路：维护每个值作为某个区间的最小值时，可以到达的区间长度。

用一个单增的单调栈从两边分别维护一遍即可。

Code:

#include <cstdio>
#define ll long long
ll max(ll x,ll y){return x>y?x:y;}
const int N=2000010;
ll read()
{ll x=0;char c;while(c<'0'||c>'9') c=getchar();while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-'0';c=getchar();}return x;
}
int s[N],tot,n;
ll a[N],l[N],r[N];
int main()
{n=read();for(int i=1;i<=n;i++)a[i]=read();for(int i=1;i<=n;i++){while(tot&&a[s[tot]]>=a[i]) l[i]+=l[s[tot--]];l[i]++;s[++tot]=i;}tot=0;for(int i=n;i;i--){while(tot&&a[s[tot]]>=a[i]) r[i]+=r[s[tot--]];r[i]++;s[++tot]=i;}ll ans=0;for(int i=1;i<=n;i++)ans=max(ans,(l[i]+r[i]-1)*a[i]);printf("%lld\n",ans);return 0;
}

2018.7.23

转载于:.html