题解

思路

设一个位置表示已经完整解释了发送序列的某个前缀。若位置 $i$ 可达，可以把 $b_i$ 当作下一段左侧的长度标记，于是跳过标记和对应数量的数据。另一方面，也可以把当前位置的数当作某一段右侧的长度标记：若该段从位置 $i-b_i$ 开始，且这个开始位置可达，则解释完该段后的位置也可达。

两类转移只依赖已经处理过的前缀，因此可以线性扫描。

做法

令可达数组的第零项为真，表示空前缀可以被解释。按顺序处理每个位置：

• 如果当前位置之前的前缀可达，并且把当前位置作为左侧标记不会越界，则把相应段末尾之后的位置标为可达。
• 如果以当前位置为右侧标记所确定的段起点合法，且该起点之前的前缀可达，则把当前位置之后的位置标为可达。

最终整个长度对应的位置可达时输出 YES，否则输出 NO。

每一种合法分段的最后一段必然属于上述两类之一，因此其前缀会逐段被标记为可达；反过来，每次转移都恰好添加一个满足长度标记规则的段，所以可达状态也一定对应合法解释。这证明了判定的充要性。

复杂度

每个位置只执行常数次转移。每个测试用例的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。