Description
$ ext{Flute}$ 很喜欢柠檬。它准备了一串用树枝串起来的贝壳，打算用一种魔法把贝壳变成柠檬。贝壳一共有 $n$ $(1≤n≤100000)$ 只，按顺序串在树枝上。为了方便，我们从左到右给贝壳编号 $1..n$ 。每只贝壳的大小不一定相同，贝壳 $i$ 的大小为 $s_i(1≤s_i≤10000)$ 。
变柠檬的魔法要求$: ext{Flute}$ 每次从树枝一端取下一小段连续的贝壳，并选择一种贝壳的大小 $s_0$。如果这一小段贝壳中大小为 $s_0$ 的贝壳有 $t$ 只，那么魔法可以把这一小段贝壳变成 $s_0t^2$ 只柠檬。$ ext{Flute}$ 可以取任意多次贝壳，直到树枝上的贝壳被全部取完。各个小段中，$ ext{Flute}$ 选择的贝壳大小 $s_0$ 可以不同。而最终 $ ext{Flute}$ 得到的柠檬数，就是所有小段柠檬数的总和。
$ ext{Flute}$ 想知道，它最多能用这一串贝壳变出多少柠檬。请你帮忙解决这个问题。
Solution
设$c_i$表示$i$位置是该颜色的第几个，发现每一个区间左右端点颜色相同，题中转移式可以写成直线：
$$f_{j-1}+s_j c_j^2 - 2s_j c_j = 2s_i c_i c_j + f_i-s_i c_i^2 - 2s_i c_i + s_i$$
题中要求最大化截距，所以对于每一种颜色维护上凸壳，因为斜率递增，所以转移点位置单调，时间复杂度$O(n)$
#include<iostream> #include<vector> #include<cstdio> using namespace std; int n,buc[10005]; double s[100005],dp[100005],c[100005]; vector<int>sta[10005]; inline int read(){ int f=1,w=0; char ch=0; while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9')w=(w<<1)+(w<<3)+ch-'0',ch=getchar(); return f*w; } inline double Y(int i){return dp[i-1]+s[i]*c[i]*c[i]-2*s[i]*c[i];} inline double X(int i){return c[i];} inline double slope(int i,int j){return (Y(j)-Y(i))/(X(j)-X(i));} inline double calc(int i,int j){return dp[j-1]+s[i]*(c[i]-c[j]+1)*(c[i]-c[j]+1);} int main(){ n=read(); for(int i=1;i<=n;i++)s[i]=read(),c[i]=++buc[(int)s[i]]; for(int i=1;i<=n;i++){ int t=s[i]; while(sta[t].size()>=2&&slope(sta[t][sta[t].size()-2],i)>=slope(sta[t][sta[t].size()-2],sta[t][sta[t].size()-1]))sta[t].pop_back(); sta[t].push_back(i); while(sta[t].size()>=2&&calc(i,sta[t][sta[t].size()-1])<calc(i,sta[t][sta[t].size()-2]))sta[t].pop_back(); dp[i]=calc(i,sta[t][sta[t].size()-1]); } printf("%lld ",(long long)dp[n]); return 0; }