自动搬运

查看原文

来自洛谷，原作者为

	CSP_Sept 私が戻ってきたのはね。 もう一度、星の音を聞くためだよ

搬运于2025-08-24 22:45:14，当前版本为作者最后更新于2023-02-18 21:57:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本题解中「平铺」指：

用一个字符串循环拼接无限次，取前 $n-1$ 个字符组成新字符串。

$\textbf{Subtask 1}$

留给 $O(T2^nn)$ 的选手们。

期望得分 10 分。

$\textbf{Subtask 2}$

留给 $O(n^2)$ 的 dp 选手们。

期望得分 40 分。

$\textbf{Subtask 3}$

容易发现，只有两种字符是有效的。

使用一个长度为 $n-1$ 的 01 串表示乐谱中的情况，对于第 $i$ 个字符，

• 为 $0$ 表示没有「重音」，即 $s_i\ne s_{i+1}$。
• 为 $1$ 表示有「重音」，即 $s_i=s_{i+1}$。

构造长为 $(n-1)$ 的 $01$ 串，每个 $1$ 的代价为 $a$，每连续 $(k-1)$ 个 $0$ 的代价为 $b$。

最优解有以下三种情况：

1. 「平铺」$0$；
2. 「平铺」长为 $(k-1)$ 的串 $000\ldots0001$；
3. 「平铺」长为 $(k-1)$ 的串 $000\ldots0001$，但是将最后一个 $1$ 改为 $0$。

考虑证明这个结论：

对于情况 2，

• 若把除了最后一个以外的 $1$ 改成 $0$ 更优，运用类比可知全部改为 $0$ 更优，于是变成情况 1（若把 $0$ 改成 $1$，无故多了一个代价 $a$，肯定不优）。
• 由于最后一个 $1$ 后面可能不满 $k-2$ 个 $0$，所以诞生了情况 3。

$\text{Q. E .D. }$

期望得分 100 分。