题解

思路

保留某个位置 $i$ 作为一个块的开头时，需要在它后面再保留 $a_i$ 个元素。若某个方案选择了更靠后的 元素作为块内容，把这些内容替换为位置 $i$ 后最早的 $a_i$ 个元素，不会改变块的合法性，还会让 后续未处理部分更长。因此总存在一个最优方案，使每个被保留的块在原序列中也是一段连续区间。

于是处理到位置 $i$ 时只有两种有必要考虑的决策：删除 $a_i$；或者把 $a_i,a_{i+1},\ldots,a_{i+a_i}$ 整段作为一个块保留。

做法

令 $f_i$ 表示只处理后缀 $a_i,a_{i+1},\ldots,a_n$ 时所需的最少删除次数，且 $f_{n+1}=0$。

• 删除位置 $i$，代价为 $1+f_{i+1}$；
• 若 $i+a_i\le n$，可以保留从 $i$ 开始的整个块，代价为 $f_{i+a_i+1}$。

取两种决策的较小值并从右向左递推，答案为 $f_1$。

子任务说明

• 当 $n\le20$ 时，可以枚举所有位置子集，检查保留下来的子序列能否按块解析，取最少删除数。
• 当所有 $a_i=1$ 时，每个块恰有两个元素，保留最长偶数长度前缀即可，答案为 $n\bmod2$。
• 一般情形使用后缀 DP。

正确性证明

由上述“内容前移”论证，存在一个最优解，其中每个保留块由原序列中的连续元素组成。因此在任意位置 $i$，若它没有被删除，就必然作为新块开头，并与紧随其后的 $a_i$ 个元素一起保留；不存在第三类 更优决策。

对后缀起点从右向左归纳。删除 $a_i$ 后，剩余问题恰是状态 $f_{i+1}$；保留以 $a_i$ 为首的合法 块后，剩余问题恰是 $f_{i+a_i+1}$。归纳假设保证两个后继状态都已是对应后缀的最优值，转移又枚举 了全部必要决策，所以 $f_i$ 最优。最终 $f_1$ 即原问题答案。

复杂度

每个位置只转移常数次。单组时间复杂度为 $O(n)$，空间复杂度为 $O(n)$；所有测试用例的总时间与 空间均为 $O(\sum n)$。