本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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$，此时可以这样转移：
$dp_{i,\min(n,k+a_k-1)} = 2$，注意 $k \lt 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]$ 的格子向后涂色得到。

最后我的解决方案。