题目大意

有 $D$ 个定音鼓，每个鼓可以调到 $1$ 到 $12$ 的音调，且鼓的音调必须严格递增。有 $N$ 个音符，每个音符在时间 $T_i$ 需要音调 $P_i$。一次只能调整一个鼓，求演奏过程中单次调整可用的最长时间的最大值。

算法思路

核心思想

状态压缩动态规划，枚举所有可能的鼓的音调组合。

关键观察

鼓的音调必须严格递增，因此有效状态数是组合数 $C(12, D)$

对于 $D \le 4$，状态数最多为 $C(12,4) = 495$，可以枚举

调整时间受限于相邻音符间时间间隔和需要调整的鼓的数量

算法步骤

1. 状态生成

用 DFS 生成所有可能的鼓的音调组合（严格递增）

用 map 将状态向量映射到整数编号

2. 状态转移

f[i][s] 表示演奏到第 $i$ 个音符时鼓的状态为 $s$ 的最大可用调整时间

初始状态：第一个音符时，所有能演奏该音符的状态初始化为无穷大

转移：$f[i][t] = max(min(f[i-1][s], (T_i - T_{i-1}) / diff(s,t)))$

diff(s,t) 表示状态 $s$ 到 $t$ 需要调整的鼓的数量

取 min 是因为整个间隔的调整时间受限于最短的“一段”时间

3. 可行性检查

flag[i][s] 表示状态 $s$ 能否演奏第 $i$ 个音符

即检查 $P_i$ 是否在状态 $s$ 的音调集合中

算法流程

预处理

生成所有合法的鼓状态

计算状态间的转移代价（需要调整的鼓数）

标记每个状态能否演奏每个音符

动态规划

初始化第一个音符的状态

按时间顺序进行状态转移

记录每个状态的最大可用调整时间

输出答案

取最后一个音符所有状态中的最大值

输出保留两位小数

复杂度分析

状态数：$K = C(12, D) \le 495$

时间复杂度：$O(N \cdot K^2)$，在 $N \le 100$ 时可接受

空间复杂度：$O(N \cdot K)$

总结

本题是状态压缩DP的典型应用：

状态设计：利用音调严格递增的性质大幅减少状态数

可行性剪枝：预先计算每个状态能否演奏每个音符

最小值约束：调整时间受限于间隔时间和需要调整的鼓数

组合枚举：DFS 生成所有合法状态

这种"状态压缩 + 组合枚举"的方法在状态空间可控的组合优化问题中非常有效，特别适合处理类似乐器和资源配置的问题。