貌似做所有的DP题都要先搞出暴力式子，再往正解上靠。。。
设(f_{i,j})为前(i)个数分(j)段的最小花费，(w_{l,r})为([l,r])全在一段的费用。
显然(j)这一维可以滚掉，于是变成(g_i=minlimits_{k=1}^{i}{f_k+w_{k,i}})做(m)遍（题目中的(k)）
这又是一个决策单调性优化的式子。还是决策二分栈吗？要不得了，因为就算知道(i,k)也没法直接算(f_k+w_{k,i})。
再次推广蒟蒻的DP优化总结
分治。总结里的概述蒟蒻也懒得再㧟一遍了。。。就说说这题的实现细节吧。
(L^AT_EX)画图？（雾
求解区间：(|gets)预处理( o|) (lfrac{qquadqquadqquaddownarrow^{mid}qquadqquadqquad}{}r)
决策区间：(Lfrac{qquadqquadqquadqquaddownarrow^{k}qquadqquadqquad}{}R)
设当前的求解区间为([l,r])，最优决策区间([L,R])。对于当前分治的中点(mid)，我们需要在([L,min(R,mid)])中暴力找到最优决策(k)。注意到从(w_{l,r})到(w_{l,r+1})或者从(w_{l,r})到(w_{l+1,r})都是可以做到(O(1))的，只要开一个桶记录当前区间每个颜色出现次数就可以啦。把指针(i)从(L)移到(min(R,mid))并不断的算(f_i+w_{i,mid})，最终可以找到(k)。
注意一点，当进入求解区间时，我们的应该要确保([L,l-1])的信息的存在，这样才能保证分治的复杂度。
于是我们考虑进子问题之前如何先处理出子问题的答案。先看左边的子问题（([l,mid-1],[L,k])）显然和当前问题的([L,l-1])是一样的。注意到我们在求(k)的时候对(w)和桶都做了修改，那么我们直接还原回来就可以进左子问题了。
而右子问题呢？（([mid+1,r],[k,R])）它要预处理的是([k,mid])，而当前的是([L,l-1])。所以我们先把右端点指针从(l-1)移到(mid)，桶和(w)都加上去，再把左端点从(L)移到(k-1)，桶和(w)都减掉，接着进去就好了。回溯的时候还是要还原到([L,l-1])，因为上一层要接着用。
注意答案是long long级别的。
代码经过了精心排版（尤其是分治那一块）
#include<cstdio>
#include<cstring>
#define RG register
#define R RG int
#define G c=getchar()
typedef long long LL;
const int N=1e5+9;
int a[N],c[N];
LL ff[N],gg[N],*f=ff,*g=gg;
inline int in(){
RG char G;
while(c<'-')G;
R x=c&15;G;
while(c>'-')x=x*10+(c&15),G;
return x;
}
void solve(R l,R r,R kl,R kr,RG LL w){//kl,kr就是决策区间
if(l>r)return;//边界
R m=(l+r)>>1,k=0,p=m<kr?m:kr,i;
for(i= l;i<=m;++i)w+=c[a[i]]++;//求k
for(i=kl;i<=p;++i)w-=--c[a[i]],g[m]>f[i]+w?g[m]=f[i]+w,k=i:0;
for(i=kl;i<=p;++i)w+=c[a[i]]++;//还原
for(i= l;i<=m;++i)w-=--c[a[i]];
solve(l,m-1,kl,k,w);
for(i= l;i<=m;++i)w+=c[a[i]]++;//调整
for(i=kl;i< k;++i)w-=--c[a[i]];
solve(m+1,r,k,kr,w);
for(i=kl;i< k;++i)++c[a[i]];//再次还原
for(i= l;i<=m;++i)--c[a[i]];
}
int main(){
R n=in(),k=in();
RG LL*tmp;
for(R i=1;i<=n;++i)//第一次直接算
f[i]=f[i-1]+c[a[i]=in()]++;
memset(c,0,(n+1)<<2);
while(--k){
memset(g,1,(n+1)<<3);
solve(1,n,1,n,0);
tmp=f;f=g;g=tmp;
}
printf("%lld
",f[n]);
return 0;
}