题解

思路

每个装置有“不用、向左、向右”三种互斥选择。小规模可直接枚举；稍大规模可把已涂色格子表示成位掩码。满分做法按位置扫描，只需记录当前最左未覆盖段的长度，以及此前向右使用的装置还能覆盖多少格。

做法

子任务 1

枚举 $3^n$ 种方向选择，合并所选区间并检查是否覆盖全部格子，取使用次数最小值。

子任务 2

令 $dp[mask]$ 表示处理若干装置后得到覆盖集合 $mask$ 的最少使用次数。逐个装置用新数组转移“不用、向左、向右”，从而保证每个装置至多使用一次。

子任务 3

令 $dp[i][j][k]$ 表示已处理前 $i$ 个位置，当前连续未覆盖段长度为 $j$，已有向右覆盖还剩 $k$ 格时的最少使用次数。对第 $i+1$ 个装置分别转移三种选择：不用会更新未覆盖段；向左可在长度不超过 $a_i$ 时补掉该段；向右会扩大剩余右覆盖。最终要求未覆盖段长度为零。

正确性证明

三种转移逐一对应每个装置的全部合法行为，且每层只处理一个新装置，所以不会重复使用。状态中的未覆盖段和剩余右覆盖包含后续决策所需的全部信息；向左操作能否补齐该段只取决于段长与 $a_i$，向右操作的未来作用只取决于剩余长度。因此所有合法方案都对应一条状态路径，所有状态路径也都对应合法方案，取最小值即为答案。

复杂度

三层算法的时间复杂度分别为 $O(3^n n)$、$O(n2^n)$、$O(n^3)$；满分算法空间复杂度为 $O(n^3)$。