题解

思路推导

每次选择都会改变后续所有入睡时刻，因此只看当前一步的贪心策略并不可靠。不过，未来只与当前是一天中的哪个时刻有关。

设 $dp_t$ 表示处理完若干次睡眠后，当前时刻为 $t$ 时能获得的最多好觉次数。对于第 $i$ 个数 $a_i$，从时刻 $t$ 可以转移到

到达的新时刻若位于 $[l,r]$，就在原答案上加一。每一层只依赖上一层，使用两个长度为 $h$ 的数组滚动即可。

正确性证明

对已经处理的睡眠次数归纳。初始时只有时刻 $0$ 可达，且好觉数为 $0$，状态正确。

假设上一层的每个 $dp_t$ 已是在时刻 $t$ 结束时的最优值。第 $i$ 次入睡只有等待 $a_i$ 或 $a_i-1$ 两种合法选择，转移恰好枚举这两种选择，并按新时刻是否属于 $[l,r]$ 增加贡献。所有到达同一新时刻的方案取最大值，因此既没有遗漏合法方案，也不会保留劣于另一方案的结果。故新一层所有状态仍然正确。

归纳完成后，对所有最终时刻取最大值，即为全部合法安排中的最大好觉次数。

做法

• 当 $n\le18$ 时，可以枚举 $2^n$ 种选择并直接模拟。
• 当 $l=0,r=h-1$ 时，每个时刻都是好时刻，答案恒为 $n$。
• 一般情形使用上述按时刻的动态规划。

独立核验程序使用另一组状态：处理到第 $i$ 次时记录前 $i$ 次共选择了多少个 $a_j-1$。此时实际时刻由前缀和与该数量唯一确定，可用 $O(n^2)$ 的转移交叉验证正式答案。

复杂度分析

时间复杂度为 $O(nh)$，空间复杂度为 $O(h)$。