LXVI.[USACO09MAR]Cleaning Up G
\(n^2\)的DP非常eazy，考虑如何优化。
首先，答案一定是\(\leq n\)的，因为一定可以每一个数单独划一组，此时答案为\(n\)。
则一组里面最多只能有\(\sqrt{n}\)个不同的数，不然平方一下就超过\(n\)了。
因此我们可以设\(pos_i\)表示不同的数有\(i\)个时，最远能够延伸到哪里。
再设\(f[i]\)表示位置\(i\)的答案。
则\(f[i]=\min\limits_{j=1}^{\sqrt{n}}(f[pos_j]+j^2)\)
关键是如何维护\(pos\)。我们只需要对于每个位置记录前驱\(pre_i\)，后继\(suf_i\)即可。如果一个位置是第一次出现，必有\(pre_i<pos_j\)；这时就应该删去第一个有\(suf_k>i\)的\(k\)。
复杂度\(O(n\sqrt{n})\)。
代码：
#include<bits/stdc++.h>
using namespace std;
int a[40100],n,m,f[40100],lim,pre[40100],suf[40100],pos[40100],val[40100],cnt[40100];
int main(){
scanf("%d%d",&n,&m),lim=sqrt(n),memset(f,0x3f3f3f3f,sizeof(f)),f[0]=0;
for(int i=1;i<=n;i++)scanf("%d",&a[i]),pre[i]=val[a[i]],suf[pre[i]]=i,suf[i]=n+1,val[a[i]]=i;
// for(int i=1;i<=n;i++)printf("(%d %d)\n",pre[i],suf[i]);
for(int i=1;i<=lim;i++)pos[i]=1;
for(int i=1;i<=n;i++)for(int j=1;j<=lim;j++){
cnt[j]+=(pre[i]<pos[j]);
if(cnt[j]>j){
cnt[j]--;
while(suf[pos[j]]<=i)pos[j]++;
pos[j]++;
}
f[i]=min(f[i],f[pos[j]-1]+j*j);
}
// for(int i=1;i<=n;i++)printf("%d ",f[i]);puts("");
printf("%d\n",f[n]);
return 0;
}