[JSOI2011]柠檬

还是先有一些约定：

• \(f_i\) 表示到消除到 \(i\) 时的最大值。
• \(c_i\) 表示当前贝壳的大小。
• \(s_i\) 表示从 \(1\) 开始到 \(i\) 有多少个贝壳与当前贝壳颜色相同。

然后，显然可以发现，我们接下来的一段的两端的颜色应当是相同的时候最优，所以就可以对不同的颜色分开讨论。

考虑对于 \(i\)，有决策点 \(j\)，当且仅当 \(c_i==c_j\)。若此时有两个决策点 \(j<k\)，此时 \(j\) 比 \(k\) 更优当且仅当： \[ \begin{aligned} f_{j-1}+c_i\times(s_i-s_j+1)^2&>f_{k-1}+c_i\times(s_k-s_j+1)^2\\ f_{j-1}+c_is_j-2c_is_is_j+c_i{s_j}^2+c_i&>f_{k-1}+c_is_k-2c_is_is_k+c_i{s_k}^2+c_i\\ f_{j-1}+c_is_j-2c_is_is_j+c_i{s_j}^2&>f_{k-1}+c_is_k-2c_is_is_k+c_i{s_k}^2\\ f_{j-1}-2c_is_is_j+c_i{s_j}^2-f_{k-1}-2c_is_is_k+c_i{s_k}^2&>c_i(s_k-s_j)\\ \frac{\Delta y}{c_i(s_k-s_j)}&>1 \end{aligned} \] 由于这些点的 \(s\) 是丹增的，所以就可以用栈维护一个上凸壳，栈定就是当点的最优决策点。

所以找出来所有决策点以后，在用决策单调性稍加处理，就可以统计答案了。

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 10;
const int maxm = 1e4 + 10;
int n, tot[maxm];
int s[maxn], c[maxn];
vector <int> stk[maxm];
ll f[maxn];

inline ll Y(int i)
{
	return f[i - 1] + 1ll * c[i] * s[i] * s[i] - 2ll * c[i] * s[i];
}

inline double slope(int i, int j)
{
	return 1.0 * (Y(i) - Y(j)) / (s[i] * c[i] - s[j] * c[j]);
}

inline ll calc(int i, int j)
{
	return f[j - 1] + 1ll * c[i] * (s[i] - s[j] + 1) * (s[i] - s[j] + 1);
}

#define t1 stk[t][stk[t].size() - 1]
#define t2 stk[t][stk[t].size() - 2]

int main()
{
	scanf ("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf ("%d", c + i);
		s[i] = ++tot[c[i]];
	}
	for (int i = 1, t; i <= n; ++i) {
		t = c[i];
		while (stk[t].size() > 1 && slope(t2, i) >= slope(t2, t1)) stk[t].pop_back();
		stk[t].push_back(i);
		while (stk[t].size() > 1 && calc(i, t1) <= calc(i, t2)) stk[t].pop_back();
		f[i] = calc(i, t1);
	}
	printf ("%lld\n", f[n]); 
}