做题时间：2022.10.15
\(【题目描述】\)
给定一个长度为 \(n(2\leq n\leq 10^5)\) 的序列，把他分成 \(k(2\leq k\leq \min(n,20))\) 个子段，每个子段的花费是其中相同元素的对数，求所有子段的花费之和的最小值。
\(【输入格式】\)
第一行两个整数 \(n,k\)
第二行 \(n\) 个整数表示序列
\(【输出格式】\)
一行一个整数表示答案
\(【考点】\)
决策单调性优化dp、莫队
\(【做法】\)
设 \(f_{i,j}\) 表示将前 \(i\) 个数分割成 \(j\) 个子段的花费，有：
\[f_{i,j}=\min\limits_{k=1}^{i}(f_{k,j-1}+val(k+1,j)) \]然后套路地使用分治去做。比较麻烦的是计算 \(val(l,r)\)，可以使用类似于莫队的思想，直接全局维护当前的求解区间 \([L,R]\)，然后每次计算的时候暴力移动左右端点即可。这相当于每层递归移动完父亲后移动儿子，因此单层的复杂度为 \(O(n)\)，总时间复杂度为 \(O(n\log n)\)
\(【代码】\)
#include<cstdio>
#include<iomanip>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=1e5+50,K=22;
int a[N],n,k;
ll f[N][K],ans;
int buc[N],L=1,R;
void add(int x){ans+=(ll)buc[x],buc[x]++;}//添加一个点
void del(int x){buc[x]--,ans-=(ll)buc[x];}//删除一个点
ll calc(int l,int r)//暴力移动并计算val[l,r]
{
while(L>l) L--,add(a[L]);
while(L<l) del(a[L]),L++;
while(R<r) R++,add(a[R]);
while(R>r) del(a[R]),R--;
return ans;
}
void dp(int l,int r,int jl,int jr,int cur)
{
if(l>r) return ;
int mid=(l+r)>>1;
int num=jl;
for(int k=jl;k<=min(jr,mid);k++){
ll t=f[k][cur-1]+calc(k+1,mid);
if(t<f[mid][cur]) f[mid][cur]=t,num=k;
}
dp(l,mid-1,jl,num,cur);
dp(mid+1,r,num,jr,cur);
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
memset(f,0x3f,sizeof f);
f[0][0]=0;
for(int i=1;i<=k;i++) dp(1,n,0,n-1,i);
printf("%lld\n",f[n][k]);
return 0;
}