Link.
做 vjudge 的题有一种美丽的窒息的感觉。
设 \(f_{i, j}\) 表示前 \(i\) 个选 \(j\) 段出来的最小代价，转移 \(f_{i, j} = \min_{0 \leq k < i} \{f_{k, j - 1} + w_{k + 1, i} \}\)，\(w_{k + 1, i}\) 是 \([k + 1, i]\) 这一段的代价，时间复杂度 \(O(n^2k)\)，然后就不会做了 /ll
观察一下 \(f_{i - 1, j} = \min_{0 \leq k < i - 1} \{f_{k, j - 1} + w_{k + 1, i - 1} \}\)，转移到 \(f_{i, j}\) 首先多了一个 \(f_{i - 1, j - 1} + w_{i - 1 + 1, i} = f_{i - 1, j - 1}\)，可以直接 \(O(1)\) 维护。然后把 \(f_{k, j - 1} + w_{k + 1, i - 1}\) 这一坨看成一个下标为 \(k\) 的序列，转移 \(w_{k + 1, i - 1} \to w_{k + 1, i}\) 只需要考虑 \(a_i\) 的贡献，这个只对 \(a_i\) 这个值的位置有影响，其它的没有影响（反正不涉及到这个值，\(first\) 和 \(last\) 不变），那么有影响的部分就是数组中的 \([1, pre_i]\)，其中 \(pre_i\) 表示 \(i\) 前面第一个和 \(a_i\) 相等的下标，因为 \(pre_i\) 之后是没有和 \(a_i\) 相等的值的。对于这个部分，\(last(a_i)\) 从 \(pre_i\) 变成了 \(i\)，增加量是 \(i - pre_i\)。
把上面这一坨抽象一下，就是维护一个区间加和区间查询最小值的玩意，直接线段树维护 \(O(n \log n)\)。
然后 \(f_{i, j}\) 只和 \(f_{i, j - 1}\) 有关，可以缩掉一维，外层循环 \(j\)，每次计算 \(f_i\) 即可。总的时间复杂度 \(O(k n \log n)\)。
一个小细节：线段树序列下标为 \(k\) 对应的是 \(w_{k + 1, i - 1}\)，要和数组下标对应，实际操作的时候操作的下标是 \([0, pre_i - 1]\)。
namespace liuzimingc {
const int N = 35005, M = 105;
#define endl '\n'
int n, k, a[N], dp[N], pre[N], pos[N];
struct segment_tree {
int l, r, val, tag;
} t[N << 2];
void push_down(int p) {
if (t[p].tag) {
t[p << 1].tag += t[p].tag;
t[p << 1].val += t[p].tag;
t[p << 1 | 1].tag += t[p].tag;
t[p << 1 | 1].val += t[p].tag;
t[p].tag = 0;
}
}
void push_up(int p) {
t[p].val = min(t[p << 1].val, t[p << 1 | 1].val);
}
void build(int p, int l, int r) {
t[p].l = l, t[p].r = r, t[p].tag = 0;
if (l == r) {
t[p].val = dp[l];
return;
}
int mid = l + r >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
push_up(p);
}
void update(int p, int l, int r, int v) {
if (l <= t[p].l && t[p].r <= r) {
t[p].val += v;
t[p].tag += v;
return;
}
push_down(p);
int mid = t[p].l + t[p].r >> 1;
if (l <= mid) update(p << 1, l, r, v);
if (r > mid) update(p << 1 | 1, l, r, v);
push_up(p);
}
int ask(int p, int l, int r) {
if (l <= t[p].l && t[p].r <= r) return t[p].val;
push_down(p);
int mid = t[p].l + t[p].r >> 1, ans = 0x3f3f3f3f;
if (l <= mid) ans = min(ans, ask(p << 1, l, r));
if (r > mid) ans = min(ans, ask(p << 1 | 1, l, r));
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
pre[i] = pos[a[i]];
pos[a[i]] = i;
}
memset(dp, 0x3f, sizeof(dp)); // 现在代码中的 dp 数组随机写 dp / f
dp[0] = 0;
for (int j = 1; j <= k; j++) {
build(1, 0, n);
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - 1];
if (pre[i]) update(1, 0, pre[i] - 1, i - pre[i]);
dp[i] = ask(1, 0, i - 1);
}
}
cout << dp[n] << endl;
return 0;
}
} // namespace liuzimingc