10 16

• 1.3
  • 将所有 \(y_i\) 按照 \(x_i\) 排序，定义 \(f_{i,j}\) 表示其中一只手在 \(y_i\) 且另一只手在 \(j\) 的最小花费，转移有两种:
    • 将 \(y_{i-1}\) 处的手移动到 \(y_i\) 处：\(f_{i,j} = \min(f_{i-1,j} + dis_{y_{i-1},y_i})\)
    • 将另一只手移动到 \(y_i\) 处: \(f_{i,y_{i-1}} = \min(\min_{j=1}^{m}(f_{i-1,j}+dis_{j,y_i}))\)
  • 其中 \(dis_{a,b}\) 表示 \(a,b\) 之间的距离，由于 \(dis_{a,b}\) 只有四种形式，所以我们可以压掉 \(f\) 的第一维上线段树优化即可
  • 对于相同时间段的钦定先后顺序，只需要强制第二个音符不进行第一种转移即可
  • 具体实现中我们可以维护 \(f_i + i，f_i，f_i - i\) 的区间 \(\min\) 即可