题意

给$n$个贝壳，可以将贝壳分成若干段，每段选取一个贝壳$s_i$，这一段$s_i$的数目为$num$，可以得到$num^2\times s_i$个柠檬，求最多能得到几个柠檬

---

可以发现只有在一段中首尾颜色相同的情况下最优，所以每次选取一段里末位的$s_i$变成柠檬，于是有$f_i=max_{j \le i}{f_{j-1}+s_i\times(pre_i-pre_j+1)^2}$ ，$pre_i$表示前$i$个贝壳里$s_i$出现了几次

令$j<k$，假设$f_{j-1}+s_i\times(pre_i-pre_j+1)^2<f_{k-1}+s_i\times(pre_i-pre_k+1)^2$，整理得到$\frac{(f_{j-1}+s_i\times (pre_j-1)^2)-(f_{k-1}+s_i\times (pre_k-1)^2)}{s_i\times (pre_j-pre_k)}<2pre_i$

左边式子为斜率，可以发现满足单调性,利用单调栈优化

时间复杂度$O(n)$

代码

#include 
    
     using namespace std;typedef long long LL;int n, s[100005], cnt[10005], pre[100005];LL dp[100005], col;vector
     
       sta[100005];inline double slope(int x, int y) {    return (double)((dp[x - 1] + col * (pre[x] - 1) * (pre[x] - 1)) - (dp[y - 1] + col * (pre[y] - 1) * (pre[y] - 1))) / (double)(col * (pre[x] - pre[y]));}int main() {    scanf("%d", &n);    int l = 1, r = 0;    for(int i = 1; i <= n; ++i) {        scanf("%d", &s[i]); pre[i] = ++cnt[s[i]];    }    for(int i = 1; i <= n; ++i) {        col = s[i]; int top = sta[col].size() - 1;        while(top > 0 && slope(sta[col][top - 1], sta[col][top]) < slope(sta[col][top], i)) sta[col].pop_back(), --top;        sta[col].push_back(i); ++top;        while(top > 0 && slope(sta[col][top - 1], sta[col][top]) < 2 * pre[i]) sta[col].pop_back(), --top;        dp[i] = dp[sta[col][top] - 1] + col * (pre[i] - pre[sta[col][top]] + 1) * (pre[i] - pre[sta[col][top]] + 1);    }    printf("%lld\n", dp[n]);    return 0;}