推(chao)式子：

令$f_i$表示以i结尾时取得的最大值,$c_i$表示$a_i$这个数在第i个位置是第$c_i$次出现，则有：

$$f_i=f_{j-1}+(c_i-c_j+1)^2*a_i$$

不妨设j>k时从j转移比从i转移更优

则有：

$$f_{j-1}+(c_i-c_j+1)^2·a_i>f_{k-1}+(c_i-c_k+1)^2·a_i$$

其中$a_i$是常数，我们考虑最后再乘回去，所以先不管它

然后化简有：

$$(f_{j-1}+(c_j-1)^2)-(f_{k-1}+(c_k-1)^2)>2c_i(c_j-c_k)$$

不妨再设$dp_i=f_{i-1}+(c_i-1)^2$

$$dp_j-dp_k>2c_i(c_j-c_k)$$

$$\frac{dp_j-dp_k}{c_j-c_k}>2c_i$$

好了于是我们把斜率搞出来了

要求最大值，所以用单调栈维护上凸壳，栈顶元素最优

附上抄来的代码

 1 //张家奇怎么又AKIOI了呀，怎么CSP也满分啊...怎么清北天天给他打电话啊...怎么会有这么强的人啊 2 #include<bits/stdc++.h> 3 #define int long long 4 #define writeln(x) write(x),puts("") 5 #define writep(x) write(x),putchar(‘ ‘) 6 using namespace std; 7 inline int read(){ 8 int ans=0,f=1;char chr=getchar(); 9 while(!isdigit(chr)){if(chr==‘-‘) f=-1;chr=getchar();}10 while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}11 return ans*f;12 }void write(int x){13 if(x<0) putchar(‘-‘),x=-x;14 if(x>9) write(x/10);15 putchar(x%10+‘0‘);16 }const int M = 1E5+5;17 int n,m,a[M];18 inline int sqr(int x){return x*x;}19 namespace Solution_1{//n^2logn的暴力转移 20 int f[M];vector<int>pos[M];21 inline int Count(int color,int l,int r){22 l=lower_bound(pos[color].begin(),pos[color].end(),l)-pos[color].begin();23 r=upper_bound(pos[color].begin(),pos[color].end(),r)-pos[color].begin()-1;24 return r-l+1;25 }inline void Solve(){26 for(int i=1;i<=n;i++)pos[a[i]].push_back(i);27 f[1]=a[1];28 for(int i=2;i<=n;i++)29 for(int j=0;j<i;j++)30 f[i]=max(f[i],f[j]+sqr(Count(a[j+1],j+1,i))*a[j+1]);31 cout<<f[n]<<endl;32  }33 }34 namespace Solution_2{35 int f[M],c[M],top,lst[M];vector<int>sta[10005];36 inline double X(int i){return a[i]*c[i];}37 inline double Y(int i){return f[i-1]+a[i]*sqr(c[i]-1);}38 inline double Slope(int i,int j){return (Y(i)-Y(j))/(X(i)-X(j));}39 inline int calc(int i,int j){return f[j-1]+sqr(c[i]-c[j]+1)*a[i];}40 #define A sta[a[i]][sta[a[i]].size()-2]41 #define B sta[a[i]][sta[a[i]].size()-1]42 inline void Solve(){43 for(int i=1;i<=n;i++)c[i]=c[lst[a[i]]]+1,lst[a[i]]=i;44 for(int i=1;i<=n;i++){45 while(sta[a[i]].size()>=2&&Slope(A,i)>=Slope(A,B))sta[a[i]].pop_back();46  sta[a[i]].push_back(i);47 while(sta[a[i]].size()>=2&&calc(i,B)<=calc(i,A))sta[a[i]].pop_back();48 f[i]=calc(i,sta[a[i]].back());49 }cout<<f[n]<<endl;50  }51 }52 signed main(){53 n=read();54 for(int i=1;i<=n;i++)a[i]=read();55 if(n<=1000)Solution_1::Solve();56 else Solution_2::Solve();57 return 0;58 }