思路
首先，最优秀的分法一定是每段两端都是这一段中最多的那个，否则可以把不是的那个踢出去单独成段肯定会更优秀。然后就成了将这个序列分段，保证每段两端元素相同的最大收益和。
用a[i]记录第i个位置上的数，用s[i]记录前i个元素中a[i]出现的次数。f[i]表示以前i个数的最大收益。
首先考虑\(n^2\)的dp。明显\(f[i]=max\{f[j]+a[i]*(s[i]-s[j]+1)^2\} (a[i]==a[j])\)
for(int i=1;i<=n;++i)
for(int j=1;j<=i;++j)
if(a[i]==a[j])
f[i]=max(f[i],f[j-1]+a[i]*(s[i]-s[j]+1)*(s[i]-s[j]+1));
然后可发现，在上面的式子中，s数组是单增的，f数组也是单增的。如果知道了两个位置x和y(x<y)。通过二分，可以找到一个now使得当以后的某个位置pos的s[pos]>now之后的所有位置用x转移会比y优秀，这时y就没用了。所以用一个单调栈维护即可。
\(O(n^2)\)代码
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const int N=100000+100;
ll read() {
ll x=0,f=1; char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
int n;
int a[N],s[N],c[N];
ll f[N];
int main() {
n=read();
for(int i=1;i<=n;++i) {
a[i]=read();
s[i]=++c[a[i]];
}
for(int i=1;i<=n;++i)
for(int j=1;j<=i;++j)
if(a[i]==a[j])
f[i]=max(f[i],f[j-1]+a[i]*(s[i]-s[j]+1)*(s[i]-s[j]+1));
cout<<f[n];
return 0;
}
\(O(n)\)代码
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<map>
#include<bits/stdc++.h>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N=100000+100;
ll read() {
ll x=0,f=1; char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
vector<int> sta[N];
int a[N],s[N],c[N];
ll f[N];
ll calc(int x,int y) {
return f[x-1]+(ll)a[x]*y*y;
}
int n;
int find(int x,int y) {//寻找x比y优秀的最早时间
int l=1,r=n;
int ans=n+1;
while(l<=r) {
int mid=l+r>>1;
if(calc(x,mid-s[x]+1)>=calc(y,mid-s[y]+1)) ans=mid,r=mid-1;
else l=mid+1;
}
return ans;
}
int main() {
n=read();
for(int i=1;i<=n;++i) {
a[i]=read();
s[i]=++c[a[i]];
}
for(int i=1;i<=n;++i) {
while(sta[a[i]].size()>=2&&find(sta[a[i]][sta[a[i]].size()-1],i)>=find(sta[a[i]][sta[a[i]].size()-2],sta[a[i]][sta[a[i]].size()-1]))
sta[a[i]].pop_back();
sta[a[i]].push_back(i);
while(sta[a[i]].size()>=2&&find(sta[a[i]][sta[a[i]].size()-2],sta[a[i]][sta[a[i]].size()-1])<=s[i]) {
sta[a[i]].pop_back();
}
int now=sta[a[i]].size();
f[i]=calc(sta[a[i]][now-1],s[i]-s[sta[a[i]][now-1]]+1);
}
cout<<f[n];
}