定义关于数字串 \(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;
}