题目大意：现有$n$条排成一行的木板，每个木板有一个目标颜色。你每次能将一个区间内的木板分别染成它们的目标颜色，而这次染色的代价为这个区间内不同目标颜色的木板的数量的平方。问将全部木板染成目标颜色的最小代价。
数据范围：$n≤50000$，颜色数量$≤50000$。
这题我们显然可以$dp$，令$f[i]$表示把前i个点覆盖完的最小代价，显然$f[i]=min(f[j-1]+w(j,i)^2)$ 其中$w(j,i)$表示区间$[i,j]$中的颜色数量。
这一题有一个隐藏条件，就是总代价不会超过$n$，这个是显然的。
所以，当区间$[i,j]$中的颜色数量$>\sqrt{n}$时，就显然不是最优的。
考虑到$f[i]$是非降的，那么我们处理一个数组$pre[i][j]$表示：从第$i$号点开始，恰好包含$j$种颜色的区间最左侧的端点编号。
我们从$1$到$\sqrt{n}$枚举$j$，每次$O(n)$的时间从右往左扫，详情见代码。
然后就愉悦地做完了，时间复杂度为$O(n*\sqrt{n})$。
#include<bits/stdc++.h>
#define M 100005
#define INF 1000000005
using namespace std; int n,a[M]={},pre[M][]={},f[M]={},cnt[M]={},sum=; int main(){
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",a+i);
for(int j=;j*j<=n;j++){
for(int i=n,k=n;~i;i--){
while(k>=&&sum<=j){
cnt[a[k]]++;
if(cnt[a[k]]==) sum++;
k--;
}
pre[i][j]=k+;
cnt[a[i]]--; if(!cnt[a[i]]) sum--;
}
}
for(int i=;i<=n;i++){
f[i]=INF;
for(int j=;j*j<=n;j++)
f[i]=min(f[i],f[pre[i][j]]+j*j);
}
printf("%d\n",f[n]);
}