Descritpion：

有排列好的 $n$ 个贝壳，每个贝壳的大小为 $s_i$ ，每次可以取出一段，并选择一个常数 $s_0$ ，如果这一小段贝壳中大小为 $s_0$ 的贝壳有 $ t $ 只，那么魔法可以把这一小段贝壳变成 $s_0\times t^2 $ 只柠檬，问最多能变出多少个柠檬。

$n\le100000,s_i\le10000$

Solution：

最终结果只与最终分的情况有关，而与分的顺序无关，于是可以设 $f[i]$ 表示分到 $i$ 表示最终能变出几个柠檬，又发现开始和结束的贝壳大小一定是一样的，不然可以把前面一段分出去获得更大价值，于是可以将相同大小的放在一起转移，记 $sum_i$ 为到 $i$ 为止 $s_i$ 出现了多少次，转移方程为： $f[i]=max\{f[j-1]+s_i\times (sum_i-sum_j+1)^2\}$

整理得 $f[j-1]+s_i\times (sum_j-1)^2=2\times s_i\times sum_i\times (sum_j-1)+f[i]-s_i\times sum_i^2$

$y=f[j-1]+s_j\times (sum_j-1)^2$ ， $k=2\times s_i\times sum_i$ ， $x=sum_j-1$ ， $b=f[i]-s_i\times sum_i^2$

发现 $k$ 单调递增， $x$ 单调递增，但是不能用单调队列维护，因为要维护上凸壳，但决策的取值点和 $x$ 增长方向不相同，因而决策不具有单调性，原来是最优解的将来还可能是最优解，于是用单调栈维护上凸壳，每次询问时在栈上二分即可，单调栈可以用 $vector$ 实现。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

#define MAXS 10010

typedef long long ll;

ll s[MAXN];

ll sum[MAXN];

ll cnt[MAXS];

vector<ll> t[MAXS];

ll f[MAXN];

typedef long double ld;

#define x(i) ((ld)sum[i] - (ld)1)

#define y(i) ((ld)f[i - 1] + (ld)s[i] * (ld)(sum[i] - 1) * (ld)(sum[i] - 1))

#define k(i) ((ld)2 * (ld)s[i] * (ld)sum[i])

#define b(i) ((ld)f[i] - (ld)s[i] * (ld)sum[i] * (ld)sum[i])

#define slope(a,b) ((y(b) - y(a)) / (x(b) - x(a)))

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%lld",&s[i]);

	for(int i = 1;i <= n;++i)sum[i] = ++cnt[s[i]];

	for(int i = 1;i <= n;++i)

	{

		while(t[s[i]].size() >= 2 && slope(t[s[i]][t[s[i]].size() - 1],t[s[i]][t[s[i]].size() - 2]) < slope(i,t[s[i]][t[s[i]].size() - 1]))t[s[i]].pop_back();

		t[s[i]].push_back(i);

		int l = 0,r = t[s[i]].size() - 1,mid;

		while(l < r)

		{

			mid = ((l + r) >> 1);

			if(k(i) < slope(t[s[i]][mid],t[s[i]][mid + 1]))l = mid + 1;

			else r = mid;

		}

		f[i] = f[t[s[i]][l] - 1] + (ll)s[i] * (ll)(sum[i] - sum[t[s[i]][l]] + 1) * (ll)(sum[i] - sum[t[s[i]][l]] + 1);

	}

	cout << f[n] << endl;

	return 0;

}