【Codeforces 868F】Yet Another Minimization Problem
动态规划，决策单调性，分治
题目大意：
给定一个数列，要将其分成恰好 $k$ 段，每段的花费为其中相同元素的对数。求最小总花费。
题解：
考虑 DP。
令 $f[i][j]$ 表示前 $i$ 个数划分为 $j$ 段的最小花费。
$f[i][j]=\min\{f[k][j-1]+w(k+1,i)\}$，其中 $w(x,y)$ 表示 $x\sim y$ 中相同元素的对数。
转移是 $O(n)$ 的，时间复杂度 $O(n^2k)$。
这个转移满足决策单调性，即若 $f[i]$ 由 $x$ 转移，$f[i+1]$ 由 $y$ 转移，那么 $x\leq y$。
证明：
假设 $x\lt y$ 且存在 $i \gt y$ 满足 $f[y][k]+w(y+1,i)\leq f[x][k]+w(x+1,i)$，$f[x][k]+w(x+1,i+1)< f[y][k]+w(y+1,i+1)$，
那么可推出 $w(x+1,i+1)-w(x+1,i)<w(y+1,i+1)-w(y+1,i)$。
其中 $w(l,r+1)-w(l,r)$ 相当于在 $a_{l\sim r}$ 中加入 $a_{r+1}$ 后的变化量。
由于 $[x+1,i]$ 的长度大于 $[y+1,i]$，因此同时插入 $a_{i+1}$ 时，前者的变化量一定不少于后者，与上面的式子矛盾。
然后我们可以分治计算 DP 值。
假设我们当前要计算 $[l,r]$ 这些位置的 DP 值，已知决策点在 $[L,R]$ 内。
我们先取 $mid=\lfloor\frac{l+r}2\rfloor$，然后求出 $mid$ 这个位置的决策点 $p$。
那么 $[l,mid-1]$ 这些位置的决策点在 $[L,p]$ 内，$[mid+1,r]$ 这些位置的决策点在 $[p,R]$ 内。递归计算即可。
考虑计算的时候 $w(l,r)$ 的值如何计算。
由于每个区间的 $mid$ 相同，即右端点相同，所以计算该区间时，每次只会增加/减少一个数。暴力计算即可。
也可以像莫队那样从之前的状态转移过来，复杂度均摊正确。
时间复杂度 $O(nk\log n)$。
Code：
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=1e5+6;
int n,k,a[N];LL dp[2][N];
namespace W{
int l,r,t[N];
LL s;
LL work(int L,int R){
while(r<R)s+=t[a[++r]]++;
while(l>L)s+=t[a[--l]]++;
while(l<L)s-=--t[a[l++]];
while(r>R)s-=--t[a[r--]];
return s;
}
}
void solve(int l,int r,int L,int R,LL*f,LL*g){
if(L>R||l>r)return;
const int mid=l+r>>1;
int p=0;
for(int i=L;i<=R&&i<mid;++i){
const LL w=W::work(i+1,mid);
if(f[mid]>w+g[i])f[mid]=w+g[i],p=i;
}
solve(l,mid-1,L,p,f,g),solve(mid+1,r,p,R,f,g);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;++i)cin>>a[i];
W::l=1,W::r=0;
memset(*dp,0x3f,(n+2)<<3);
**dp=0;
for(int i=1;i<=k;++i)memset(dp[i&1],0x3f,(n+2)<<3),solve(1,n,0,n-1,dp[i&1],dp[i&1^1]);
cout<<dp[k&1][n]<<'\n';
return 0;
}