CF2004G 题解

CTHOOH / 2024-09-20 / 原文

题意

定义关于数字串 $s$ 的函数 $f(s)$ 表示将 $t$ 切分为 $m$ 段，要求 $m$ 是偶数，假设这些字符串分别为 $t_1, t_2, \ldots, t_m$，有 $s = t_1 + t_2 + \ldots + t_m$。定义 $A^x$ 表示 $\underbrace{AA\ldots AA}_{x~\text{times}}$，求一种划分方式，使得 $t_2^{t_1} + t_4^{t_3} + \ldots + t_m^{t_{m - 1}}$ 最短。

现在给定长度为 $n$ 的字符串 $S$ 和一个正整数 $k$，对每个 $i = 1, 2, \ldots, n - k + 1$，求出 $f(s[i, i + 1, \ldots, i + k - 1])$。

首先考虑 $k = n$ 的情况，容易观察到对于 $i$ 为奇数，$t_i$ 一定小于 $10$，否则可以将后一位分给 $t_{i + 1}$，一定更优。根据该性质，可以考虑 dp 并设计出 dp 方程，设 $f_{i, j}$ 表示考虑前 $i$ 位，现在的 $t_{k}$ 等于 $j$ 的答案，有转移：

刚刚结束一段 $t_k$，则 $j = 0$，有 $f_{i, j} = \min\{f_{i - 1, k} + k\}$，其中 $k \in [1, 9]$。
延续关于 $t_k$ 的选择，对于 $j \in [1, 9]$，有 $f_{i, j} = \min\{f_{i - 1, j} + j\}$。
开始一段新的 $t_k$，有 $f_{i, t_j} = \min\{f_{i - 1, 0}\}$。

答案是 $f_{n, 0}$。

注意到这个转移是可以矩乘辅助转移的，可以设计出矩阵：

\[\begin{bmatrix} f_{i, 0} & f_{i, 1} & f_{i, 2} & \ldots & f_{i, 9} \end{bmatrix} \times \begin{bmatrix} +\infty & +\infty & +\infty & \ldots & +\infty \\ 1 & 1 & +\infty & \ldots & +\infty\\ 2 & +\infty & 2 & \ldots & +\infty\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 9 & +\infty & +\infty & \ldots & 9 \end{bmatrix} = \begin{bmatrix} f_{i + 1, 0} & f_{i + 1, 1} & f_{i + 1, 2} & \ldots & f_{i + 1, 9} \end{bmatrix} \]

要把转移矩阵的第一行第 $t_i$ 列设成 $0$，注意这里的矩阵乘法为 $(\min, +)$ 运算，即 $A \times B = C$ 实际上是：

\[C_{i, j} = \min_{k = 0}^9 A_{i, k} + B_{k, j} \]

设 $w = 10$，可以在 $O(nw^3)$ 的复杂度内计算出 $k = n$ 时的答案，考虑扩展到 $k < n$ 的情况。

有一个经典 trick（这个 trick 在 P6717 和 P1117 中都有运用），就是将序列按照块长为 $k - 1$ 分为若干块，这样每一个长度为 $k$ 的子区间一定都是一块的前缀和一块的后缀拼起来的。

所以可以预处理每个块的前缀积和后缀积，每次查询时乘起来即可。时间复杂度仍为 $O(nw^3)$。

但 $O(nw^3)$ 常数过大，写出来会被卡常，考虑优化。由于矩阵中只有 $O(w)$ 个位置不是 $+\infty$，所以对这 $O(w)$ 个位置分别转移即可，时间复杂度优化到了 $O(nw^2)$，可以通过。

代码

#include <bits/stdc++.h>

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

constexpr int N = 10;

constexpr int inf = 1E9;

struct Matrix {
    std::vector<std::vector<int>> a;

    Matrix() {
        Init(0);
    }
    Matrix(int k) {
        Init(k);
    }

    void Init(int k) {
        a.assign(N, std::vector<int>(N, inf));
        if (k == 1) {
            for (int i = 0; i < N; ++i) {
                a[i][i] = 0;
            }
        }
    }

    auto &operator[](int x) {
        return a[x];
    }
} ;

Matrix appendr(Matrix pre, int x) {
    Matrix res;
    
    for (int i = 0; i < N; ++i) {
        for (int j = 1; j < N; ++j) {
            res[i][0] = std::min(res[i][0], pre[i][j] + j);
            res[i][j] = std::min(res[i][j], pre[i][j] + j);
        }
    }
    for (int i = 0; i < N; ++i) {
        res[i][x] = std::min(res[i][x], pre[i][0]);
    }

    return res;
}

Matrix appendl(Matrix pre, int x) {
    Matrix res;

    for (int i = 1; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            res[i][j] = std::min(res[i][j], i + std::min(pre[0][j], pre[i][j]));
        }
    }

    for (int i = 0; i < N; ++i) {
        res[0][i] = std::min(res[0][i], pre[x][i]);
    }

    return res;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, k;
    std::cin >> n >> k;
    
    std::string s;
    std::cin >> s;

    std::vector<Matrix> suf(n);

    for (int l = 0, r = 0; l < n; l = r + 1) {
        r = std::min(n - 1, l + k - 2);

        Matrix res = 1;
        for (int i = l; i <= r; ++i) {
            res = appendr(res, s[i] - '0');
            if (i + 1 >= k) {                  
                int ans = inf;
                for (int x = 0; x < N; ++x) {
                    ans = std::min(ans, suf[i - k + 1][0][x] + res[x][0]);
                }
                std::cout << ans << " ";
            }
        }

        suf[r] = 1;
        for (int i = r; i >= l; --i) {
            suf[i] = appendl(suf[i + (i < r)], s[i] - '0');
        }
    }

    return 0;
}