「题解」CF868F Yet Another Minimization Problem

AtomAlpaca

题意
题解

题意

给定一个序列 $a$ ，要把它分成恰好 $k$ 个子段。每个代价的费用是其中相同元素的对数。求所有子段的代价之和的最小值。

link

题解

首先有一个暴力的 dp:

$f_{i, j} = \min_{k = 2}^{i}{f_{k - 1, j - 1} + v(k, i)}$

其中 $v(l, r)$ 是 $[l, r]$ 这一子段的代价。

这个形式让人不禁四边形不等式了起来。我们考虑证明 $v$ 满足四边形不等式。

我们不妨设 $w(l, r, s, t)$ 是 $[l, r]$ 中的元素和 $[s, t]$ 中元素相等的对数。那么对于 $a \le b \le c \le d$

$\begin{aligned} & v(a, c) + v(b, d) - (v(a, d) + v(b, d))\\ =& 2v(b, c) + v(a, b) + v(c, d) + w(a, b, b, c) + w(b, c, c, d) \\ -& 2v(b, c) - v(a, b) - v(c, d) - w(a, b, b, c) - w(b, c, c, d) - w(a, b, c, d) \\ =& -w(a, b, c, d) \\ \le& 0 \end{aligned}$

因此得到 $v$ 满足四边形不等式。于是我们可以利用决策单调性来做这个问题。

现在问题在于我们很难 $O(1)$ 地求解 $v$ 。那么我们考虑用类似莫队的思路，维护一个桶每次移动两个端点。然后我们发现对于每个分治区间，我们指针移动的次数是区间长度的一半，而分治的深度一共是 $\log$ 层，因此算下来我们的指针只会移动 $O(nk \log n)$ 次。

至此我们可以在 $(nk \log n)$ 的时间复杂度解决这个问题。可以把 dp 的第二维用滚动数组优化掉，不过这题并不卡空间。

#include <bits/stdc++.h>

typedef long long ll;
const int MAX = 1e5 + 5;
const ll INF = 1e16;
int n, k, L = 1, R = 0; ll res;
ll f[MAX][2]; int a[MAX], b[MAX];

ll w(int l, int r)
{
    while (R < r) { ++R; res += b[a[R]]++; }
    while (L > l) { --L; res += b[a[L]]++; }
    while (R > r) { res -= --b[a[R]]; --R; }
    while (L < l) { res -= --b[a[L]]; ++L; }
    return res;
}

void solve(int l, int r, int s, int t, int x)
{
    if (l > r) { return ; }
    int k = l + ((r - l) >> 1), p = s; ll mn = INF;
    for (int i = s; i <= std::min(k, t); ++i)
    {
        if (f[i - 1][x ^ 1] + w(i, k) < mn) { p = i; mn = f[i - 1][x ^ 1] + w(i, k); }
    }
    f[k][x] = mn;
    solve(l, k - 1, s, p, x); solve(k + 1, r, p, t, x);
}

int main()
{
    memset(f, 0x7f, sizeof(f)); f[0][0] = 0;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); }
    for (int i = 1; i <= k; ++i) { solve(1, n, 1, n, i & 1); }
    printf("%lld", f[n][k & 1]);
}

Table of contents

题意

题解