本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-07-15 12:10:27

题解思路：

我们可以用 dp，状态转移为： $$dp_{i , j} = \min\{dp_{k , j - 1} + w_{k + 1 , i}\}$$ 但时间复杂度至少为 $\mathcal{O(n^2k)}$。 我们怎么用数据结构去优化呢？

1. 我们就按 $j$ 分层。 每次从 $j - 1$ 的状态推出 $j$。 则 $f_i=dp_{i , j - 1}$。 而 $g_i = \min(f_k + w_{k + 1 , i})$。
2. 怎么维护： 设 $h_k = f_k + w_{k + 1 , i}$。 当 $i \to i + 1$。 分两种情况：

1.当前数没有出现过，则贡献为 $0$。 2.若他出现过，那么他的贡献就是加上了 $i + 1 -$ 上一次出现的位置。

这就是前缀加以及前缀最小值。

那么我们用线段树来维护 $h$ 数组即可。

AC CODE:

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef int ll;
const int N = 35100;
int n , k;
int last[N] , pre[N] , f[N];
struct node {
	ll t;
	ll val;
}seg[N * 4];
int a[N];
void update (int id) {
	seg[id].val = min(seg[id * 2].val , seg[id * 2 + 1].val);
}
void settag (int id , int t) {
	seg[id].val = seg[id].val + t;
	seg[id].t = seg[id].t + t;
}
void pushdown (int id) {
	if (seg[id].t != 0) {\/\/标记非空
		settag (id * 2 , seg[id].t);
		settag (id * 2 + 1 , seg[id].t);
		seg[id].t = 0;
	}
}
void build (int id , int l , int r) {
	seg[id].t = 0;
	if (l == r) {
		seg[id].val = f[l];
	}else {
		int mid = (l + r) >> 1;
		build (id * 2 , l , mid);
		build (id * 2 + 1 , mid + 1 , r);
		update (id);
	}
}
void modify (int id , int l , int r , int ql , int qr , int t) {
	if (l == ql && r == qr){ settag(id , t); return;}
	int mid = (l + r) \/ 2;
	pushdown (id);
	if (qr <= mid) modify (id * 2 , l , mid , ql , qr , t);
	else if (ql > mid) modify (id * 2 + 1 , mid + 1 , r , ql , qr , t);
	else {
		modify (id * 2 , l , mid , ql , mid , t);
		modify (id * 2 + 1 , mid + 1 , r, mid + 1 , qr ,t);
	}
	update (id);
}
ll query (int id , int l , int r , int ql , int qr) {
	if (l == ql && r == qr) return seg[id].val;
	int mid = (l + r) \/ 2;
	pushdown (id);
	if (qr <= mid) return query (id * 2 , l , mid , ql , qr);
	else if (ql > mid) return query (id * 2 + 1 , mid + 1 , r , ql , qr);
	else {
		return min(query (id * 2 , l , mid , ql , mid) , query (id * 2 + 1 , mid + 1 , r, mid + 1 , qr));
	}
}
int main() {
	scanf ("%d%d" , &n , &k);
	for (int i = 1; i <= n; ++ i) {
		scanf ("%d" , &a[i]);
		last[i] = pre[a[i]];
		pre[a[i]] = i;
	}
	f[0] = 0;
	for (int i = 1; i <= n; ++ i) f[i] = 1 << 30;
	for (int j = 1; j <= k; ++ j) {
		build (1 , 0 , n);
		for (int i = 1; i <= n; ++ i) {
			if (last[i] != 0) modify (1 , 0 , n , 0 , last[i] - 1 , i - last[i]);
			f[i] = query (1 , 0 , n , 0 , i - 1);
		}
	}	
	printf ("%d\n" , f[n]);
	return 0;
}