考虑朴素 dp：设 \(f_{i,j}\) 表示分了 \(j\) 段且第 \(j\) 段的末尾是 \(i\) 的最小花费。
有转移：\(f_{i,j} \gets \min\limits_{k=0}^{i-1} f_{k,j-1} + cost(k+1,i)\)，其中 \(cost(l,r)\) 表示将 \([l,r]\) 分一段的花费。分层计算，每次从 \(j - 1\) 推到 \(j\)。
考虑线段树上维护 \(f_{k,j-1}+cost(k+1,i)\)。当 \(cost(k+1,i-1) \to cost(k+1,i)\) 时，只有 \(k \in [0,lst_i-1]\) 的 \(f_{k,j-1}\) 会增加 \(i - lst_i\)，其中 \(lst_i\) 表示最大的 \(j\) 满足 \(j \in [1,i-1]\) 且 \(a_j = a_i\)。前缀加、前缀查询 \(\min\) 即可。
时间复杂度 \(O(kn \log n)\)。
code
/*
p_b_p_b txdy
AThousandSuns txdy
Wu_Ren txdy
Appleblue17 txdy
*/
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 35050;
const ll inf = 0x3f3f3f3f3f3f3f3fLL;
int n, m, a[maxn], pre[maxn], lst[maxn];
ll f[maxn];
namespace SGT {
ll tree[maxn << 2], tag[maxn << 2];
void pushup(int x) {
tree[x] = min(tree[x << 1], tree[x << 1 | 1]);
}
void pushdown(int x) {
if (!tag[x]) {
return;
}
tree[x << 1] += tag[x];
tree[x << 1 | 1] += tag[x];
tag[x << 1] += tag[x];
tag[x << 1 | 1] += tag[x];
tag[x] = 0;
}
void build(int rt, int l, int r) {
tag[rt] = 0;
if (l == r) {
tree[rt] = f[l];
return;
}
int mid = (l + r) >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
pushup(rt);
}
void update(int rt, int l, int r, int ql, int qr, ll x) {
if (ql <= l && r <= qr) {
tree[rt] += x;
tag[rt] += x;
return;
}
pushdown(rt);
int mid = (l + r) >> 1;
if (ql <= mid) {
update(rt << 1, l, mid, ql, qr, x);
}
if (qr > mid) {
update(rt << 1 | 1, mid + 1, r, ql, qr, x);
}
pushup(rt);
}
ll query(int rt, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) {
return tree[rt];
}
pushdown(rt);
int mid = (l + r) >> 1;
ll res = inf;
if (ql <= mid) {
res = min(res, query(rt << 1, l, mid, ql, qr));
}
if (qr > mid) {
res = min(res, query(rt << 1 | 1, mid + 1, r, ql, qr));
}
return res;
}
}
void solve() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
lst[i] = pre[a[i]];
pre[a[i]] = i;
}
mems(f, 0x3f);
f[0] = 0;
for (int j = 1; j <= m; ++j) {
SGT::build(1, 0, n);
for (int i = 1; i <= n; ++i) {
if (lst[i]) {
SGT::update(1, 0, n, 0, lst[i] - 1, i - lst[i]);
}
f[i] = SGT::query(1, 0, n, 0, i - 1);
}
}
printf("%lld\n", f[n]);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}