【题解】 CF868F Yet Another Minimization Problem

· · 题解

刚刚学完DP的各种玄学优化，所以过来赶紧水一发题解巩固一下知识。

题意

有一个长度为 n 的序列，要求将其分成 k 个子段，每个子段的花费是子段内相同元素的对数，求最小花费。

解法

首先想到暴力的DP，设 f[i][j] 表示长度为 i 的序列分成 j 个子段后的最小花费，显然有： f[i][j]=\min \{f[k][j-1] + val(k+1,i)\},k\in[1,i] ，val 表示的是这一段的花费。

如果直接用上面的转移方程计算，复杂度是 \Theta (n^2k) 。妥妥的TLE

所以我们要考虑优化。

可以看出，随着 i 的增加，如果 j 不变，显然 f[i][j] 单调不降。所以， f[i][j] 在向右转移时具有决策单调性。

可以简单口胡一下：如果后面的子段对答案有贡献，答案应该增加；否则，由于答案取的是前一段的最小值并且要加上一个 val ，所以不会导致答案比以前更小，即使 val = 0 ，答案也是不降的。

由此，我们可以祭出这篇题解的主角：分治决策优化DP。

由于答案单调，所以我们可以二分，设现在等待转移的区间为 [l,r] ，可以转移过来的决策所在区间为 [ql,qr] ，那么对于每一次查找，我们可以定义一个 mid 为 l,r 的中点，然后递归求解。

如图：

分治优化DP模板——代码片段（摘自OI-WIKI）

void DP(int l, int r, int k_l, int k_r) {
  int mid = (l + r) / 2, k = k_l;
  // 求状态f[mid]的最优决策点
  for (int i = k_l; i <= min(k_r, mid - 1); ++i)
    if (w(i, mid) < w(k, mid)) k = i;
  f[mid] = w(k, mid);
  // 根据决策单调性得出左右两部分的决策区间，递归处理
  if (l < mid) DP(l, mid - 1, k_l, k);
  if (r > mid) DP(mid + 1, r, k, k_r);
}

对于本题，我们可以用同样的思路，设 qmid 为最优决策所在的位置，最开始置为 ql ，然后遍历 ql 到 qr ，遇到答案可以更新的时候就更新答案和 qmid ，之后递归求解。

inline void solve(int l, int r, int ql, int qr, int tot) { 
    //l, r, ql, qr 如上所述，tot 代表当前的子段数。
    if (l > r) return;
    int mid = (l + r) >> 1, qmid = ql;
    for (ri i = ql; i <= min(qr, mid); i++) {
        int las = f[i - 1][(tot - 1) & 1] + val(i, mid); //计算此时决策区间对应的决策
        bool updated = (las < f[mid][tot & 1]); // 是否可以更新
        if (updated) f[mid][tot & 1] = las, qmid = i; // 更新答案和决策位置
    }
    solve(l, mid - 1, ql, qmid, tot);
    solve(mid + 1, r, qmid, qr, tot); // 递归求解
}

降低了DP的复杂度后，考虑怎样维护每个子段的花费。对于类似的计数问题，可以用暴力莫队求解。

不了解莫队的看这里——莫队 - CG__HeavenHealer 的博客 - 洛谷博客 (luogu.com.cn)（自己推销自己）

莫队维护贡献数代码片段：

namespace mocap {
int L = 1, R, ans, cnt[N], a[N];
inline void add(int x) { ans += cnt[x], cnt[x]++; }
inline void del(int x) { cnt[x]--, ans -= cnt[x]; }
inline int val(int l, int r) {
    while (L > l) add(a[--L]);
    while (L < l) del(a[L++]);
    while (R > r) del(a[R--]);
    while (R < r) add(a[++R]);
    return ans;
}
}  // namespace mocap

有了这些，就可以求解本题了。

对了，还有一个小优化——第二维可以用滚动数组优化。

Code：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ri register int
const int N = 1e5 + 10, K = 25;
inline int read() {
    ri x = 0, f = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar())
        if (ch == '-') f = -1;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    return f * x;
}
int f[N][2];
namespace mocap {
int L = 1, R, ans, cnt[N], a[N];
inline void add(int x) { ans += cnt[x], cnt[x]++; }
inline void del(int x) { cnt[x]--, ans -= cnt[x]; }
inline int val(int l, int r) {
    while (L > l) add(a[--L]);
    while (L < l) del(a[L++]);
    while (R > r) del(a[R--]);
    while (R < r) add(a[++R]);
    return ans;
}
}  // namespace mocap
using namespace mocap;
inline void solve(int l, int r, int ql, int qr, int tot) {
    if (l > r) return;
    int mid = (l + r) >> 1, qmid = ql;
    for (ri i = ql; i <= min(qr, mid); i++) {
        int las = f[i - 1][(tot - 1) & 1] + val(i, mid);
        bool updated = (las < f[mid][tot & 1]);
        if (updated) f[mid][tot & 1] = las, qmid = i;
    }
    solve(l, mid - 1, ql, qmid, tot);
    solve(mid + 1, r, qmid, qr, tot);
}
signed main() {
    int n = read(), k = read();
    for (ri i = 1; i <= n; i++) a[i] = read();
    memset(f, 0x3f, sizeof(f));
    f[0][0] = 0;
    for (ri i = 1; i <= k; i++) solve(1, n, 1, n, i & 1);
    printf("%lld\n", f[n][k & 1]);
    return 0;
}
/*
7 3
1 1 3 3 3 2 1

10 2
1 2 1 2 1 2 1 2 1 2

13 3
1 2 2 2 1 2 1 1 1 2 2 1 1
*/