[BZOJ4709][JSOI2011]柠檬(斜率优化DP)

显然选出的每一段首尾都是相同的，于是直接斜率优化，给每个颜色的数开一个单调栈即可。

 #include<cstdio>

 #include<vector>

 #include<cstring>

 #include<algorithm>

 #define rep(i,l,r) for (int i=(l); i<=(r); i++)

 typedef long long ll;

 using namespace std;

 const int N=;

 ll n,ans,a[N],f[N],lst[N],top[N],cnt[N];

 struct P{ ll x,y; };

 vector<P>s[N];

 bool Cmp(P a,P b,P c){ return (b.y-a.y)*(c.x-b.x)<=(c.y-b.y)*(b.x-a.x); }

 int main(){

     freopen("bzoj4709.in","r",stdin);

     freopen("bzoj4709.out","w",stdout);

     scanf("%lld",&n);

     rep(i,,n) scanf("%lld",&a[i]),cnt[i]=cnt[lst[a[i]]]+,lst[a[i]]=i;

     rep(i,,n) if (s[a[i]].size()==) s[a[i]].push_back((P){,});

     rep(i,,n){

         int p=a[i]; P tmp=(P){*p*cnt[i],f[i-]+p*cnt[i]*cnt[i]-*p*cnt[i]};

         while (top[p]> && Cmp(s[p][top[p]-],s[p][top[p]],tmp)) top[p]--,s[p].pop_back();

         top[p]++; s[p].push_back(tmp);

         while (top[p]> && (s[p][top[p]].x-s[p][top[p]-].x)*cnt[i]>=s[p][top[p]].y-s[p][top[p]-].y)

             top[p]--,s[p].pop_back();

         f[i]=s[p][top[p]].y-s[p][top[p]].x*cnt[i]+p+*p*cnt[i]+p*cnt[i]*cnt[i]; ans=max(ans,f[i]);

     }

     printf("%lld\n",ans);

     return ;

 }