P9087 「SvR-2」音符 题解

CSP_Sept · 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。

期望得分 100 分。