题意
定义一个数组的 \(cost\) 为数组中出现过的每个元素的最后一个位置减第一个位置。
\[cost(array) = \sum_{x\in set(array)}last(x) - first(x) \]给定一个 \(N\) 个数的数组 \(A\)，将其分为 \(K\) 段，求最小 \(cost\)。
题解
设 \(dp_{i, j}\) 为前 \(i\) 个数分为 \(j\) 段的最小 \(cost\)。
状态转移：枚举 \(k\)， 表示将区间 \([1, k]\) 分为 \(j - 1\)段，最后还有一段 \([k + 1, i]\)。
\[dp_{i, j} = \min_{k=j-1}^{i-1} (dp_{k, j-1} + cost(k + 1, i)) \]for j in [1, K + 1)
for i in [j, N + 1)
for k in [j - 1, i)
dp[i][j] = min(dp[i][j], dp[k][j - 1] + cost(k + 1, i))
复杂度为 \(N ^ 2 K\)，考虑使用数据结构优化。
发现线段树能维护区间 \(\min\)，则设 \(f_{i, j, k} = dp_{k, j-1} + cost(k + 1, i)\)，令线段树维护对于当前 \(j, i\) 所需要的 \(f_k\) 。
\[dp_{i, j} = \min_{k=j-1}^{i-1} (f_{i, j, k}) \]for j in [1, K + 1)
for i in [j, N + 1)
dp[i][j] = segtr_fk.min(j - 1, i - 1)
假设当遍历到 \(j, i - 1\) 时，线段树维护着正确的信息，在由 \(i-1\) 到 \(i\) 时，应如何更新线段树：
\[f_k = dp_{k, j - 1} + cost(k + 1, i - 1) + dist(last_{a_i}, cur_{a_i}) \]发现对于 \(k < last_{a_i}\) 的 \(f_k\)，\(A_i\) 不是最后一段区间的第一次出现，所以 \(f_k\) 要加上 \(dist(last_{a_i}, cur_{a_i})\)。
而对于 \(k \geq last_{a_i}\) 的 \(f_k\)，\(A_i\) 是最后一段区间的第一次出现，\(f_k\) 不变。
for j in [1, K + 1)
for i in [j, N + 1)
segtr_fk.add(1, last[i], i - last[i])
dp[i][j] = segtr_fk.min(j - 1, i - 1)
发现每层的 \(f_k\) 都由 \(dp_{k, j - 1}\) 为初值，在遍历 \(i\) 时加上 \(dist\) 更新。因此当从第 \(j - 1\) 层到第 \(j\) 层时，\(f\) 应初始化为 \(dp_{j-1}\)。
for j in [1, K + 1)
segtr_fk.build(dp[][j-1])
for i in [j, N + 1)
segtr_fk.add(1, last[i], i - last[i])
dp[i][j] = segtr_fk.min(j - 1, i - 1)
代码
void solve()
{
int N, K;
std::cin >> N >> K;
std::vector<int> A(N + 1);
std::vector<int> pre(N + 1);
std::vector<int> last(N + 1);
for (int i = 1; i <= N; i++)
{
std::cin >> A[i];
last[i] = pre[A[i]];
pre[A[i]] = i;
}
std::vector<i64> dp(N + 1);
// 初始化 j = 1
for (int i = 1; i <= N; i++)
{
dp[i] = dp[i - 1];
if (last[i])
{
dp[i] += i - last[i];
}
}
for (int j = 2; j <= K; j++)
{
LazySegmentTree<i64, op, e, i64, mp, comp, id> f(dp);
for (int i = j; i <= N; i++)
{
if (last[i])
{
f.apply(1, last[i], i - last[i]);
}
dp[i] = f.prod(j - 1, i);
}
}
std::cout << dp[N] << '\n';
}