題目：

思路：

下面給個經(jīng)典的 DP 式子不多說了：
\(f_i\)：\([1,i]\) 取完的最大價值。
\(qz(x,y)\)：\([1,y]\) 中 \(s_i=x\) 的數(shù)量。

移項套個斜率優(yōu)化就完了。

細(xì)節(jié)：

單調(diào)棧太陰了！下面有個 hack：

11
2 10 2 2 10 2 2 10 2 2 2
ans：128

眾所周知 \(x,k\) 都單調(diào)的題我們可以用單調(diào)隊列維護(hù)。
但是這題是上凸包且 \(k\) 遞增，手畫一下，我們會發(fā)現(xiàn)我們實際上決策點是從右端點開始縮。總的看下來是個單調(diào)棧。

代碼：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int QAQ=1e5+7,ovo=1e4+7;
int n,s[QAQ];
vector<int> qz[ovo];
int qzh(int s,int i) {return upper_bound(qz[s].begin(),qz[s].end(),i)-qz[s].begin();}
struct dian {int x,y;} ;
vector<dian> zhan[ovo];
const double inf=1e18;
double xie(dian a,dian b)
{
	if(a.x==b.x) return (b.y>=a.y)?inf:-inf;
	return (1.0*b.y-1.0*a.y)/(1.0*b.x-1.0*a.x);
}
int l[ovo],r[QAQ],f[QAQ],ans;
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>s[i],qz[s[i]].push_back(i);
	for(int i=1;i<=10000;i++) zhan[i].push_back({0,0});
	for(int i=1;i<=n;i++)
	{ 
		int ccx=qzh(s[i],i);
		int k=2*s[i]*ccx;
		while(l[s[i]]<r[s[i]]&&xie(zhan[s[i]][r[s[i]]-1],zhan[s[i]][r[s[i]]])<=k)
			r[s[i]]--;
		f[i]=s[i]*ccx*ccx+zhan[s[i]][r[s[i]]].y-k*zhan[s[i]][r[s[i]]].x;
		int swl=qzh(s[i+1],i);
		dian nw={swl,f[i]+s[i+1]*swl*swl};
		while(l[s[i+1]]<r[s[i+1]]&&
			xie(zhan[s[i+1]][r[s[i+1]]-1],zhan[s[i+1]][r[s[i+1]]])<=
								xie(zhan[s[i+1]][r[s[i+1]]-1],nw))
			r[s[i+1]]--;
		++r[s[i+1]];
		if(zhan[s[i+1]].size()<=r[s[i+1]]) zhan[s[i+1]].push_back(nw);
		else zhan[s[i+1]][r[s[i+1]]]=nw;
		ans=max(ans,f[i]);
	}
	cout<<ans;
	return 0;
}