题解

思路

按顺序处理 Boss。未来只与已经处理到的位置以及下一回合由谁行动有关，因此可以建立两类位置状态。每个回合只能击败一个或两个 Boss。

做法

令 dp[i][who] 表示已经击败前 $i$ 个 Boss、下一回合由 who 行动时，朋友已使用的最少跳过点。初始在位置 $0$ 且朋友先行动。

从每个状态枚举本回合长度 $1$ 或 $2$。若轮到朋友，新增代价等于这一段中困难 Boss 的数量；若轮到本人，新增代价为零。随后位置前进，行动者切换。答案是处理完 $n$ 个 Boss 后两个行动者状态的较小值。

正确性证明

任意合法游戏过程唯一对应于一串回合长度，每个长度为一或二，行动者交替。动态规划从初始状态枚举了所有这样的长度序列；朋友回合对每个困难 Boss 恰加一个跳过点，本人回合不加，故路径代价与实际方案完全一致。反之，每条 DP 路径都构成合法回合安排。因此在每个状态取最小值，最终得到全部合法方案中的最少跳过点。

复杂度分析

状态数为 $2(n+1)$，每个状态有至多两条转移，时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

子任务说明

• $n\le20$ 时枚举所有回合长度序列。
• 每组全零时答案为 0；每组全一时答案为 $\lceil n/3\rceil$。
• 满数据使用位置与行动者两状态动态规划。