[JSOI2011]柠檬

DP

---

题面

给定一段长度为$n$的序列$a$，需要把它分为任意多段。
对于每一段，需要选出一个数$p$，若$p$在该段中出现$k$次，则该段贡献为$pk^2$。
最大化贡献和。

• $n\leq10^6,x\leq10^5$

解析

orz GXZlegend
显然有个性质：每一段的两端同为$x$。
因为两端多出的数不可能对该段有贡献，提出它们以期望对其他段产生贡献，才能实现贡献最大化。

则可设状态为$f_i$表示前$i$个数产生的最大贡献，$S_i$表示在第$i$个位置这个数是第几次出现（出现次数的前缀和）。
有方程式

$$f_i=max\{f_{j-1}+a_i*(S_i-S_j+1)^2\}(j<i,a_j=a_i)$$
看起来$O(n^2)$很虚啊。
这时就要考虑斜率优化了。

原式为

$$f_i=f_{j-1}+a_i*(S_i-S_j+1)^2$$
于是“参变量分离”，与$j$有关的项放到$y,x$项，无关的放到$k,b$项。
于是化为 $$f_i=f_{j-1}+a_i*(S_i^2+(S_j-1)^2-2*S_i*(S_j-1)$$
$$f_{i-1}+a_i(S_j-1)^2=2*a_iS_i*(S_j-1)-a_iS_i^2+f_i$$
其中$k=2S_i,y=f_{i-1}+a_i(S_j-1)^2,x=a_i(S_j-1),k=a_iS_i,b=f_i-a_iS_i^2$
我们可以维护一个单调栈，栈顶维护最优决策。

• 栈顶$k$比因新加入元素而产生的$k$小，就弹栈。
• 新加入元素，进栈。
• 栈顶$k$小于$2S_i$，就弹栈。
• 取栈顶运算

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=1e5+100;
ll n,c[N],s[N],num[N],x[N],y[N],dp[N];
vector<int>Q[N/10];
il ll gi()
{
   re ll x=0,t=1;
   re char ch=getchar();
   while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
   if(ch=='-') t=-1,ch=getchar();
   while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
   return x*t;
}
il double slope(re int a,re int b){ return ((double)(y[a]-y[b]))/(x[a]-x[b]);}
int main()
{
  n=gi();
  fp(i,1,n) c[i]=gi(),s[i]=++num[c[i]];
  fp(i,1,n)
    {
      re int col=c[i],top=Q[col].size()-1;
      x[i]=(s[i]-1)*col;y[i]=x[i]*(s[i]-1)+dp[i-1];
      while(top>0&&slope(Q[col][top-1],Q[col][top])<slope(Q[col][top],i)) Q[col].pop_back(),--top;
      Q[col].push_back(i);++top;
      while(top>0&&slope(Q[col][top-1],Q[col][top])<2*s[i]) Q[col].pop_back(),--top;
      re int t=Q[col][top];
      dp[i]=dp[t-1]+col*(s[i]-s[t]+1)*(s[i]-s[t]+1);
    }
  printf("%lld\n",dp[n]);
  return 0;
}