题解

思路

能否在某天安排活动只与前一天做了什么有关。设置三个状态，分别表示处理完当前前缀后最后一天休息、参加比赛或健身时的最少休息天数。

做法

初始尚未处理任何一天时，视为休息状态代价为 $0$，另外两个状态不可达。对每一天：

• 新的休息状态等于三个旧状态最小值加 $1$；
• 若当天有比赛，新的比赛状态可由旧休息或旧健身状态转移；
• 若当天健身房开放，新的健身状态可由旧休息或旧比赛状态转移。

不可用的活动状态保持无穷大。处理完全部天数后取三个状态的最小值。

正确性证明

三个状态按最后一天的选择将所有合法安排互斥且完整地分类。休息可以接在任意旧状态之后并新增一天休息；比赛只能接在非比赛状态后，健身只能接在非健身状态后，恰好对应题目限制。每次转移对所有合法前驱取最小值，因此由前缀归纳可知每个状态都保存其类别的最优方案。最终取三类最小值即为全局最少休息天数。

复杂度分析

时间复杂度为 $O(n)$，额外空间复杂度为 $O(1)$。

子任务说明

• $n\le15$ 时可枚举每天的全部决策。
• 没有值 3 时每天至多一种活动可选，可直接扫描同类活动段。
• 满数据使用三状态线性动态规划。