题解 P7291 【「EZEC-5」人赢 加强版】

pigstd · 2021-01-27 12:09:10 · 题解

官方题解

• 对于一个 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;
}