题目大意

你在玩一个音游，有 $n$ 个音符依次落下，第 $i$ 个音符落在位置 $p_i$。你有两只手，每只手可以覆盖一个长度为 $L$ 的区间 $[x, x+L]$。游戏开始时两只手都在 $[0, L]$ 位置。

在音符落下的间隙，你可以移动双手，从 $[x, x+L]$ 移动到 $[y, y+L]$ 需要耗费 $|x-y|$ 的体力。

求打到所有音符所需的最小体力消耗。

算法思路

核心思想：状态空间动态规划

本题采用状态空间搜索 + 剪枝优化的策略：

• 状态表示：用 $(x, y, c)$ 表示左手在 $x$、右手在 $y$，已消耗体力为 $c$ 的状态
• 状态转移：对于每个音符，如果当前状态无法覆盖该音符，则分别移动左手或右手来覆盖

关键优化

1. 可行性剪枝：如果当前手的位置已经能覆盖音符，则直接保留该状态
2. 支配关系剪枝：对于两个状态 $(x_1, y_1, c_1)$ 和 $(x_2, y_2, c_2)$，如果：$$c_1 + |x_1 - x_2| + |y_1 - y_2| \geq c_2$$ 则状态1被状态2支配，可以剔除

算法流程

初始化：now = {(0, 0, 0)}
for 每个音符 p:
    ne = []
    for 每个状态 (x, y, c) in now:
        if (x ≤ p ≤ x+L) 或 (y ≤ p ≤ y+L):
            直接保留状态
        else:
            生成移动左手的新状态
            生成移动右手的新状态
    now = 对ne进行剪枝后的状态集合
输出 now 中最小代价

复杂度分析

• 最坏情况下状态数可能达到 $O(2^n)$
• 但由于 $L \leq 50$ 且使用了有效的剪枝策略，实际状态数得到很好控制
• 每个音符处理的时间复杂度为 $O(k^2)$，其中 $k$ 是状态数量

代码实现要点

1. 状态表示：使用结构体 Hands{x, y, c}
2. 移动策略：
   • 如果手在音符左边：移动到 $p-L$
   • 如果手在音符右边：移动到 $p$
3. 剪枝方法：通过比较代价和曼哈顿距离来剔除被支配的状态

示例分析

对于样例：

n=4, L=1
p=[6, 3, 7, 1]

最优解为 $9$，移动路径：

• 左手：$[0,1] \to [5,6] \to [6,7]$（花费 $6$）
• 右手：$[0,1] \to [2,3] \to [1,2]$（花费 $3$）

该算法通过维护可能的状态集合，逐步更新并剪枝，最终找到最小代价解。