看心情填坑

网上还没有题解，随便写写，顺便庆祝一下RANK1

$O(n^{2})$的DP很好想，用s[i]表示a[i]在i位置上的出现是第几次$dp[i]=max(dp[j-1]+(s[i]-s[j]+1)^{2}*a[i])$

非常显然这个东西是有单调性的，s[i]变大的时候相对较小的j会变优。所以我们可以写一个类似于斜率的东西。

$(s-s[i])^2*x+dp[i-1]>=(s-s[j])^2*x+dp[j-1]$

$(2*s-s[i]-s[j])*(s[j]-s[i])*x>dp[j-1]-dp[i-1]-1$

$2*s>(dp[j-1]-dp[i-1]-1)/x/(s[j]-s[i])+s[i]+s[j]$

对于每个a[i]都维护一个栈，保持决策最优性就行了。这里我是用链表维护的。

#include<cstdio>
#include<queue>
using namespace std;
int n;
int a[100005],head[10005],Head[100005],nex[100005],s[100005];
long long dp[100005];
inline int read(){
    int ret=0;char c=getchar();
    while((c>'9')||(c<'0'))c=getchar();
    while((c>='0')&&(c<='9'))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
    return ret;
}
inline long long check(int i,int j,int x){return 1LL*(s[j]-s[i]+1)*(s[j]-s[i]+1)*x+dp[i-1];}
inline long long work(int i,int j,int x){return (dp[j-1]-dp[i-1]-1)/x/(s[j]-s[i])+s[i]+s[j];}
int main(){
	n=read();
	for(int i=1;i<=n;i++){
		int x=read();s[i]=s[Head[x]]+1;Head[x]=i;
		if((head[x]==0)||(check(head[x],i,x)<check(i,i,x))){
			while((nex[head[x]])&&(work(head[x],i,x)>=work(nex[head[x]],head[x],x)))head[x]=nex[head[x]];
			nex[i]=head[x];head[x]=i;
		}
		while((nex[head[x]])&&(check(nex[head[x]],i,x)>check(head[x],i,x)))head[x]=nex[head[x]];
		dp[i]=check(head[x],i,x);
	}
	printf("%lld",dp[n]);
}