CF1927G 题解

__vector__ · 2024-02-10 00:02:21 · 题解

距离上次赛时 AC 提交被 hack 过去了近 1.5 年，写篇题解纪念一下。分类讨论漏了一种情况都能过 pretests，难怪最终只过了这么点人。
在此感谢 160cm 对我赛时代码的 hack 数据，帮我找出我的错误。

大概思路

相信很多人读完题就能想到用 dp。
由于有 n 个格子从左到右，每个格子分别决策，所以初步设想使用 dp_i 代表假如以 i 结尾（换句话说，n=i），答案是多少。

那么转移则从 1 到 n 枚举 i，然后从 [0,i-1] 依次枚举 j，计算从 dp_j 转移到 dp_i 的答案。

这里有一个致命的问题，因为即使是最优方案下解决前 i 个，但前 i 个格子的涂色有可能延伸到 i+1 或以后，而刚才设计的状态无法考虑此情况，从而导致答案算大。

另外，是否可以将状态更改为 dp_i 表示答案？这里进行一些分析。前 i 个涂满的考虑到每个格子只能决策一次，转移的时候（假设当前计算 n = i 的答案，从第 n = j 的答案转移），新操作的格子只能在 [j+1,i] 选择，而这样既需要考虑最多前多少个格子可能被操作过，也需要考虑实际覆盖了前多少个格子。而本段开头设计的状态不能表示最多前多少个格子可能被操作过，所以是错误的。

另外如果有大佬设计了一维状态的 dp，请评论区回复。

最后，我设计的状态是 dp_{i,j} 代表 n=i（即最多只操作前 i 个格子），覆盖了前 j 个格子的最小操作次数。

转移方法（以下方程默认等于号的实际作用是 checkmin）：

• 第 i 个向左涂： dp_{i,\max(y,i)} = \min(dp_{k,y})$，注意 $k \lt i,y \ge i-a_i
• 第 i 个向右涂： dp_{i,\max(y,\min(n,i+a_i-1))} = \min(dp_{k,y})$，注意 $k \lt i,y \ge i-1
• 第 i 个不涂： dp_{i,y} = \min(dp_{k,y})$，注意 $k \lt i,y \ge i

还有一种特殊情况，在样例的 testcase11 中可以看见。
这种情况就是 a_i \ge i，此时可以这样转移：

此时好像可以结束了？

如果你是这场比赛的选手，并且是 rated，那么这将是一个沉痛的教训（对不起我赛前临时改成了 unrated），因为这里漏掉了一种 pretests 中没有出现的情况。

注意，对于当前需要求解的 dp_{i,j}，不仅可以从 dp_{k \lt i,y \in [1,n]} 等第一维小于 i 的状态转移，还有可能从 dp_{i,l \lt j} 通过选择一个位置在 [j+1,i-1] 的格子向后涂色得到。

最后我的解决方案。