Luogu

分析

首先有一个显然的性质：每一段左右端的贝壳大小一定相同，而且这一段的 $s_0$ 一定是左右端贝壳的大小。因为如果不是这样的话，我们显然可以把端点单独成一段，然后答案会变大。

设 $dp_i$ 表示前 $i$ 个贝壳最多可以得到多少柠檬，$c_i$ 表示 $i$ 是第几个 $a_i$ 大小的柠檬，容易得到状态转移方程
$$
dp_i=\max_{j=1}^i\left\{dp_{j-1}+a_i(c_i-c_j+1)^2\right\}
$$
把 $\max$ 里的东西拆开，并把所有项分为三类：

• 与 $j$ 无关的：$a_ic_i\!^2+2a_ic_i+a_i$
• 只和 $j$ 有关的：$dp_{j-1}+a_ic_j\!^2-2a_ic_j$（注意， $a_i=a_j$）
• 既和 $i$ 有关又和 $j$ 有关的：$-2a_ic_ic_j$

令 $pre_i=a_ic_i\!^2+2a_ic_i+a_i$，$k_i=2c_i$，$x_i=a_ic_i$，$y_i=dp_{i-1}+a_ic_i\!^2-2a_ic_i$，那么状态转移方程改写为：
$$
dp_i=pre_i+\max_{j=1}^{i}\left\{-k_ix_j+y_j\right\}
$$
因为要求的是最大值，所以维护上凸壳；因为 $x_i$ 单增、$k_i$ 单增，所以用单调栈维护上凸壳，栈顶为最优决策。

注意每次要把自己先加到单调栈中去再取栈顶转移。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#define re register
#define sqr(x) ((x)*(x))
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10,V=10000+10;

int n,a[N],o[V],c[N];
int dp[N];
vector<int> Q[V];

inline int X(int i) { return a[i]*c[i]; }
inline int Y(int i) { return dp[i-1]+a[i]*c[i]*c[i]-2*a[i]*c[i]; }
inline double slope(int i,int j) {
    return 1.0*(Y(i)-Y(j))/(X(i)-X(j));
}
inline int calc(int i,int j) {
    return dp[j-1]+a[i]*sqr(c[i]-c[j]+1);
}

#define A Q[t][Q[t].size()-2]
#define B Q[t][Q[t].size()-1]

signed main() {
    n=read();
    for (re int i=1;i<=n;++i)
        a[i]=read(),c[i]=c[o[a[i]]]+1,o[a[i]]=i;
    for (re int i=1;i<=n;++i) { int t=a[i];
        while (Q[t].size()>=2&&slope(A,i)>=slope(A,B)) Q[t].pop_back();
        Q[t].push_back(i);
        while (Q[t].size()>=2&&calc(i,B)<=calc(i,A)) Q[t].pop_back();
        dp[i]=calc(i,Q[t].back());
    }
    printf("%lld\n",dp[n]);
    return 0;
}