【LG5504】[JSOI2011]柠檬

题面

洛谷

题解

考虑\(dp\)，令\(f_i\)表示\(dp\)到第\(i\)位且在第\(i\)位分段的最大值。

我们令题面中的\(s_i\)为\(a_i\)，那么对于一个转移点\(j\)，显然\(a_i=a_j\)，因为多余的颜色肯定无法产生贡献，不如不选。

令\(c_i\)为位置\(i\)的颜色第几次出现。

那么有转移方程：

\[f_i=f_{j-1}+a_i(c_i-c_j+1)^2
\]

推下式子：

\[f_i=f_{j-1}+a_i(c_i^2+(c_j-1)^2-2c_i(c_j-1))\\
\Leftrightarrow f_{j-1}+a_j(c_j-1)^2=2a_ic_i(c_j-1)+f_i-a_ic_i^2
\]

将这个式子看作一个一次函数\(y=kx+b\)，那么在这个式子中，\(y=f_{j-1}+a_j(c_j-1)^2,x=c_j-1,k=2a_ic_i,b=f_i-a_ic_i^2\)。

要使\(f_i\)尽量大，则\(b\)要尽量大，所以对于\((x,y)\)我们维护相邻两点斜率递减的上凸壳。

而对于同种颜色，它的斜率\(k\)必是递增的，所以由斜率优化的那套理论，相邻两点斜率小于\(k\)的那一段我们不需要，又因为凸壳上斜率递减，那么我们对每种颜色直接维护单调栈，每次取栈顶即为答案。

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <vector>

using namespace std;

inline int gi() {

    register int data = 0, w = 1;

    register char ch = 0;

    while (!isdigit(ch) && ch != '-') ch = getchar();

    if (ch == '-') w = -1, ch = getchar();

    while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar();

    return w * data;

}

const int MAX_N = 1e5 + 5;

int N, a[MAX_N], c[MAX_N], bln[MAX_N];

long long f[MAX_N], X[MAX_N], Y[MAX_N];

long double slope(int i, int j) {

	return (long double)(Y[j] - Y[i]) / (X[j] - X[i]);

}

vector<int> q[MAX_N];

int top[MAX_N], mx;

int main () {

#ifndef ONLINE_JUDGE

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

#endif

	N = gi();

	for (int i = 1; i <= N; i++) c[i] = ++bln[a[i] = gi()], mx = max(mx, a[i]);

	for (int i = 1; i <= mx; i++) q[i].push_back(0), top[i] = 0;

	for (int i = 1; i <= N; i++) {

		int col = a[i];

		while (top[col] && slope(q[col][top[col] - 1], q[col][top[col]])

			                   <= slope(q[col][top[col]], i)) --top[col];

		if ((int)q[col].size() == ++top[col]) q[col].push_back(i);

		else q[col][top[col]] = i;

		while (top[col] && slope(q[col][top[col] - 1], q[col][top[col]]) <= 2.0 * a[i] * c[i]) --top[col];

		int j = q[col][top[col]];

		f[i] = f[j - 1] + 1ll * col * (c[i] - c[j] + 1) * (c[i] - c[j] + 1);

		X[i + 1] = c[i + 1] - 1, Y[i + 1] = f[i] + 1ll * a[i + 1] * (c[i + 1] - 1) * (c[i + 1] - 1);

	}

	printf("%lld\n", *max_element(&f[1], &f[N + 1]));

    return 0;

}