Description
有 \(n\) 个人在车站等车，第 \(i\) 个人到达车站的时间是 \(t_i\)。现在有一辆车，需要 \(m\) 单位的时间把所有正在等车的人运到另一站并返回。例如，假设车子在 \(t\) 时刻发车，则所有满足 \(t_i\leq t\) 且正在等车的人都会上车。之后车会在 \(t+m\) 时刻返回，可以选择在该时刻不做停留再次发车。最小化所有人等车时间和。
\(n\leq 500,m\leq 100,t_i\leq 4\times 10^6\)
Solution
容易想到令 \(dp_i\) 表示最后一趟车在时刻 \(i\) 出发的最小等车时间和。得到方程
\[dp_i=\min_{j\leq i-m} dp_{j}+\sum_{j<t\leq i} cnt_{t}*(i-t)
\]
其中 \(cnt_t\) 表示时刻 \(t\) 到达车站的人数，那么答案是
\[\min_{t\geq \max t_i} dp_{t}
\]
对于人来说，他至多等待 \(m\) 个时间单位。否则的话可以通过在该趟之前插入一趟，会严格优于原来的方案。于是可能最优情况中发车的时刻只可能是某个 \(t_i\) ，以及 \(t_i\) 后面的那一段，即区间 \([t_i,t_i+m)\)。于是算答案的时候，只需要枚举到 \(t_{max}+m\)。另外，转移的时候若对于当前的 \(i\)，区间 \((i-m,i]\) 都没有人到达，于是后面那一项为 \(0\)，可以直接从 \(dp_j\) 的前缀最小值转移，其中 \(j\leq i-m\)。所以现在会计算后面那一项的转移只有至多 \(nm\) 个。
对于车来说，两辆车发车时间不会超过 \(2m\)，否则可以在中间插入一趟。于是 \(dp_i\) 只需要从 \(j\in(i-2*m,i-m]\) 的 \(dp_j\) 转移。
于是总的复杂度为 \(O(T+nm^2)\)。