显然分出来的每段两端颜色相同，否则把一边归给旁边的答案不变劣，于是可以$O(n^2)$地dp了：设$dp[i]$表示到第$i$个位置为止的最优解，$dp[i]=dp[j]+a[i]*(s[j]-s[i]+1)^2$ $[a[i]==a[j]]$，其中s是每种颜色出现次数的前缀和
写成斜率的形式，然后发现对每个颜色来说，斜率$k=a_i*s_i$单增，横坐标$x=2*(s_j-1)$单增，对每个颜色用单调栈维护上凸壳并在上面二分求解
1 #include<cstdio> 2 #include<vector> 3 #include<cstring> 4 #include<algorithm> 5 #define lli long long 6 using namespace std; 7 const int N=100005,M=10005; 8 int n,a[N],s[N],sz[M]; 9 lli dp[N]; vector<int> stk[M]; 10 int Top(int x) 11 { 12 return *stk[x].rbegin(); 13 } 14 int Sec(int x) 15 { 16 return stk[x][stk[x].size()-2]; 17 } 18 int Spare(int x) 19 { 20 return stk[x].size()>=2; 21 } 22 lli Calc(int x,int y) 23 { 24 return dp[x-1]+1ll*a[x]*y*y; 25 } 26 int Point(int x,int y) 27 { 28 int l=1,r=n,ret=n+1; 29 while(l<=r) 30 { 31 int mid=(l+r)/2; 32 if(Calc(x,mid-s[x]+1)>=Calc(y,mid-s[y]+1)) ret=mid,r=mid-1; 33 else l=mid+1; 34 } 35 return ret; 36 } 37 int main() 38 { 39 scanf("%d",&n); 40 for(int i=1;i<=n;i++) 41 scanf("%d",&a[i]); 42 for(int i=1;i<=n;i++) 43 { 44 int x=a[i]; 45 s[i]=++sz[x]; 46 while(Spare(x)&&Point(Sec(x),Top(x))<=Point(Top(x),i)) 47 stk[x].pop_back(); 48 stk[x].push_back(i); 49 while(Spare(x)&&Point(Sec(x),Top(x))<=s[i]) 50 stk[x].pop_back(); 51 dp[i]=Calc(Top(x),s[i]-s[Top(x)]+1); 52 } 53 printf("%lld",dp[n]); 54 return 0; 55 }