本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-07 01:06:49

倒开不幸被卡。

G 被 hack 了，请忽略以下。

一张图描述状态：

G

可以想到 dp 做法，并且看起来最重要的两个量是：

1. 当前的结尾位置 $i$
2. 前 $i$ 个涂满，且延伸到 $j \ge i$ 位置同样全部涂满。

设状态 $dp_{i,j}$ 代表以 $i$ 结尾，前 $j$ 个涂满的最小代价。

以下对 dp 赋值默认是 chkmin

考虑转移：

• 第 $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$

做完了。

简单分析一下，本算法复杂度 $O(n^3)$，最多 $10^4$ 组数据，$n \le 100$，$n$ 总和最多 $1000$，为了使运算量最大，出题人应该设置 $10$ 个 $n=100$ 的数据，此时运算量 $10^7$，稳过。

A-F

A-E 没做，F 一直 WA。