题意理解

我们有 $n$ 个音符依次落在位置 $p_1, p_2, \dots, p_n$。两只手各能覆盖一个长度为 $L$ 的区间，初始都在 $[0, L]$。移动一只手从 $[x, x+L]$ 到 $[y, y+L]$ 需要花费 $|x-y|$ 的体力。要求打到所有音符的前提下最小化总体力消耗。

关键观察：

• 每个音符必须被至少一只手覆盖
• 手的移动是连续的，代价是曼哈顿距离
• $L$ 很小（最多 50），这是算法的突破口

核心思路

关键观察 1：状态设计

由于 $L$ 很小，我们可以利用这个性质设计状态：

设 $dp[i][a][b]$ 表示处理完前 $i$ 个音符，左手覆盖区间 $[x_i + a, x_i + a + L]$，右手覆盖区间 $[x_i + b, x_i + b + L]$ 的最小代价，其中 $a, b \in [-L, L]$。

这里 $x_i$ 是第 $i$ 个音符的位置，$a, b$ 表示相对于当前音符的偏移量。

关键观察 2：状态转移

从 $i$ 到 $i+1$，我们需要将手移动到能覆盖第 $i+1$ 个音符的位置：

对于每个可能的新偏移量 $a', b'$：

$$dp[i+1][a'][b'] = \min\{dp[i][a][b] + |\Delta_1| + |\Delta_2|\} $$

其中 $\Delta_1 = (p_i + a) - (p_{i+1} + a')$，$\Delta_2 = (p_i + b) - (p_{i+1} + b')$

约束条件：第 $i+1$ 个音符必须被至少一只手覆盖，即：

$$\min(a', b') \leq 0 \leq \max(a', b') + L$$

关键观察 3：优化策略

直接 DP 的状态数是 $O(n \cdot L^2)$，转移是 $O(L^2)$，总复杂度 $O(n \cdot L^4)$ 不可接受。

优化思路：

• 使用线段树维护状态的最小值
• 利用问题的单调性
• 减少不必要的状态

算法框架

方法一：基于相对位置的 DP

设 $f[i][d]$ 表示处理完前 $i$ 个音符，两只手的相对位置差为 $d$ 时的最小代价。

状态定义更精妙：由于两只手的移动是对称的，我们可以固定一个参考系。

方法二：离散化 + 线段树优化

1. 离散化：将所有可能的手位置离散化
2. 状态设计：$dp[i][x]$ 表示处理完前 $i$ 个音符，某只手在位置 $x$ 时的最小代价（另一只手的位置隐含确定）
3. 线段树优化：使用线段树维护区间最小值，加速状态转移

方法三：决策单调性优化

观察发现，最优解中手的移动具有单调性：手不会无意义地来回移动。

可以利用这个性质设计 $O(nL)$ 或 $O(n \log n)$ 的算法。

复杂度分析

• 状态数：$O(n \cdot L^2)$
• 转移优化：通过数据结构优化到 $O(\log n)$ 或 $O(L)$ 每次转移
• 总复杂度：$O(nL^3)$ 优化到 $O(nL^2 \log n)$ 或更好

在 $n \leq 50000, L \leq 50$ 时，$O(nL^2)$ 的算法是可接受的。

实现细节

状态压缩技巧

由于 $L$ 很小，我们可以：

• 将 $a, b$ 映射到 $[0, 2L]$ 的整数
• 使用位运算加速
• 利用缓存友好性

边界情况处理

• 初始状态：$dp[0][0][0] = 0$，其他为无穷大
• 音符覆盖检查：确保每个音符都被覆盖
• 坐标范围：$p_i$ 很大但差值可能很小

总结

本题的核心在于：

1. 利用数据范围：$L$ 很小是算法设计的关键
2. 状态设计：巧妙的相对位置表示
3. 优化技巧：数据结构加速状态转移
4. 问题转化：将几何覆盖问题转化为序列决策问题

这是一个典型的 动态规划优化 题目，需要：

• 对状态设计的深刻理解
• 熟练运用数据结构优化
• 对问题性质的敏锐洞察

符合集训队互测题目对算法优化能力的高要求。