Ranom 数字 题解

思路

字符数值只有五种。若从右向左扫描，已经处理的后缀只需保留其中最大字符，就能判断当前字符应加还是应减。一次修改再增加一个二元状态。

做法

子任务 1：非递增字符串

原字符串的所有字符均为正贡献。枚举修改位置和新字符。对每个位置维护其左侧五种字符的数量；新字符与原右邻字符共同决定左侧外部最大值。左侧所有小于该最大值的字符改为负贡献，其余仍为正贡献。用五个计数即可在 $O(5)$ 时间评估一个候选修改。

子任务 2：枚举修改

枚举“不修改”以及每个位置的五种新字符。对每个候选字符串从右向左重算其值，取最大值即可。

子任务 3：状态 DP

维护 dp[used][mx]：已经处理完某个后缀，使用修改次数为 used，后缀最大字符编号为 mx 时可得到的最大贡献。

从右向左处理原字符 $x$，枚举把它保留为 $x$，或在尚未修改时改成任意 $y$。若 $y<mx$，本位贡献 $-v_y$；否则贡献 $v_y$。新状态的最大字符为 $\max(mx,y)$。初始空后缀的贡献为零，把最大字符视为 A 不影响转移，因为不存在比 A 更小的字符。最终在所有“修改零次或一次”的状态中取最大值。

复杂度

子任务 1 的时间复杂度为 $O(5|s|)$、空间复杂度为 $O(1)$；子任务 2 的时间复杂度为 $O(5|s|^2)$、空间复杂度为 $O(|s|)$；满分 DP 的时间复杂度为 $O(25|s|)$、空间复杂度为 $O(1)$。多组数据的复杂度按长度总和计算。

正确性证明

引理 1　处理某个位置时，其贡献正负只由该字符与右侧最大字符的比较决定。

证明　题目规定该字符为负贡献，当且仅当右侧存在严格更大的字符；这恰等价于右侧最大字符严格大于它。∎

引理 2　dp[used][mx] 包含对应后缀在给定修改次数和最大字符下的最优值。

证明　对处理长度归纳。空后缀结论成立。加入当前字符时，转移枚举了保留字符和所有合法的一次修改；由引理 1 正确计算本位贡献，并用 $\max(mx,y)$ 得到新后缀最大字符。所有合法方案恰进入一个转移，取最大值后保持最优性。∎

定理　算法得到的答案是至多修改一个字符后的最大 Ranom 值。

证明　由引理 2，扫描完整个字符串后，每个合法零次或一次修改方案都被某个 DP 状态覆盖，且每个状态保存这类方案的最大值。对全部终态取最大即为全局最优值。∎