[JSOI 2011]柠檬

Description

题库链接

给你一个长度为 \(n\) 的序列 \(s_i\)，你可以将他分为若干段，每一段的价值为 \(st^2\)，其中 \(s\) 表示你指定的一个数，\(t\) 表示这个数在这一段中出现的次数。你需要最大化价值和。

\(1\leq n\leq 100000,1\leq s_i\leq 10000\)

Solution

首先最优分出来的这一段两端一定是颜色相同的。

于是我们可以按颜色来 DP，设 \(f_i=\max\limits_{j\leq i,s_j=s_i}\{f_{j-1}+s_i(sum_i-sum_j+1)^2\}\)。其中 \(sum\) 表示该颜色个数的前缀和。

这个平方式子是可以斜率优化的，把平方拆开后可以化成 \(y=kx+b\)。因为需要最大化 \(f_i\)，那么就要最小化截距。由于 \(k\) 是单调递减的，因此要维护一个下凸包，并且决策点在凸包上往左移。

（其实就是四边形不等式 \(w\) 是满足 \(\geq\) 的，并且 DP 值取 \(\max\)。原理戳这）

因此用单调栈维护即可。

Code

#include 
#define ll long long
#define x(a) (s[a])
#define y(a) (-f[a-1]-1ll*t*s[a]*s[a]+2ll*t*s[a])
#define pop pop_back
#define push push_back
using namespace std;
const int N = 100000+5;

int n, l[N], c[N], s[N];
vector S[N];
ll f[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &c[i]), s[i] = s[l[c[i]]]+1, l[c[i]] = i;
    for (int i = 1; i <= n; i++) {
        int t = c[i], sz;
        while ((sz = S[t].size()) >= 2 &&
         (y(S[t][sz-1])-y(i))*(x(S[t][sz-2])-x(i)) <= (y(S[t][sz-2])-y(i))*(x(S[t][sz-1])-x(i))) S[t].pop();
        S[t].push(i);
        while ((sz = S[t].size()) >= 2 && (y(S[t][sz-1])-y(S[t][sz-2])) >= -2ll*t*s[i]*(x(S[t][sz-1])-x(S[t][sz-2]))) S[t].pop();
        f[i] = f[S[t][(sz = S[t].size())-1]-1]+1ll*t*(s[i]-s[S[t][sz-1]]+1)*(s[i]-s[S[t][sz-1]]+1);
    }
    printf("%lld\n", f[n]);
    return 0;
}