自动搬运

查看原文

来自洛谷，原作者为

	pigstd Hello, the cruel world.

搬运于2025-08-24 22:28:27，当前版本为作者最后更新于2021-01-27 12:09:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

官方题解

• $f(x,y)=k_x\times x (x = y)$ 直接扫一遍即可，接下来考虑 $x \ne y$ 的情况。
• 对于一个 $i$ 来说 ,如果 $j1 < j2$ 且 $k_{j1} < k_{j2}$，那么显然除了 $y= j2$ 的时候，$x = j1$没有$x=j2$ 更优， 则从后往前找 $k_i$ 最大值， 如果更新了就把当前位置和存入一个序列，对于每一个 $i$ 匹配这个序列里第一位置 $> i$ 的，然后更新最大值就可以。
• 正确性证明：实际上是对于每个 $k_i$ 作为较小值更新答案，对于 $i$ 来说只有那个序列第一个位置 大于它的才会对答案有效更新，不是中和 $<i$ 的肯定不会更优，而在序列中 $>i$ 的只有相邻是效更新答案，因为如果和后面的匹配更优，那后面的和这个相邻的匹配会比这个匹配更优。
• 具体实现：

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;

const int M=1e7+10;
int n,a[M],ans;

#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

int f(int x,int y)
{
	return (x+y)*min(a[x],a[y]);
}

signed main()
{
	n=read();
	for (int i=1;i<=n;i++)a[i]=read(),ans=max(ans,a[i]*i);
	for (int i=n-1,l=n;i>=1;i--)
	{
		ans=max(ans,f(i,l));
		if (a[i]>a[l])l=i;
	}
	cout<<ans;
	return 0;
}