首先要冷静下来发现这仅仅是在划分区间。显然若有相邻的数字相同应当划分在同一区间。还有一个显然的性质是区间的两端点应该相同且选择的就是端点的数。瞬间暴力dp就变成常数极小100002了。可以继续斜率优化然而懒了。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define N 100010 char getc(){char c=getchar();while ((c<‘A‘||c>‘Z‘)&&(c<‘a‘||c>‘z‘)&&(c<‘0‘||c>‘9‘)) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() { int 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<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } int n,m,a[N],b[N],cnt[N],p[N],pre[N]; ll f[N]; int main() { #ifndef ONLINE_JUDGE freopen("bzoj4709.in","r",stdin); freopen("bzoj4709.out","w",stdout); const char LL[]="%I64d\n"; #else const char LL[]="%lld\n"; #endif n=read(); for (int i=1;i<=n;i++) a[i]=read(); for (int i=1;i<=n;i++) { int t=i; while (t<n&&a[t+1]==a[i]) t++; m++,b[m]=a[i],cnt[m]=t-i+1,pre[m]=p[a[i]],p[a[i]]=m; i=t; } for (int i=1;i<=m;i++) { int s=0; for (int j=i;j;j=pre[j]) { s+=cnt[j]; f[i]=max(f[i],f[j-1]+1ll*b[i]*s*s); } } cout<<f[m]; return 0; }
原文：https://www.cnblogs.com/Gloid/p/9951507.html