2025 Summer Day10

Content：dp优化

Date：2025.7.26

例题

直接单调队列维护即可，具体操作如下：

提交记录：link

定义 $dp_{i}$ 表示第 $i$ 个任务完成所花费的最小代价。转移如下：

dp_{i} = \min_{1 \le j \le i} dp_{j} + (s + T_i - T_{j-1}) \times (F_{n} - F{j - 1})

对于本题数据范围 $n \le 3000$ ， $O(n^2)$ 可过。

提交记录：link

$dp$ 的方式和定义与前面相同，但是 $O(n^2)$ 的复杂度无法接受，所以考虑优化。

将 $dp$ 的式子拆开，发现：

dp_{i} = \min_{1 \le j \le i} dp_{j} + F_{i}T_{i} - F_{j}T_{i} + F_{n}s - F_{j}s

移项，得：

dp_{j} = (T_{i} + s)F_{j} + (dp_{i} - F_{i}T_{i} - F_{n}s)

很明显可以用斜率优化，单调队列维护下凸壳即可。

提交记录：link

注意数据范围， $\lvert T_i \rvert \le 2^8$ ，所以 $T_{i}+s$ 不具有单调性，所以上面面直接维护的方法不可做。于是我们考虑直接维护整个下凸壳，对于转移时，二分查找就可以了。

提交记录：link

我们定义 $dp_{i,j}$ 表示到第 $i$ 天走到了第 $j$ 个城市的最小平方和。之所以这样定义，是因为：

\begin{aligned} s^2 \times m^2 &= \frac{\sum_{i} (s_i - \overline{s})^2}{m} \times m^2 \\ &= \frac{(\frac{\sum_i s_i}{m})^2 - 2 \times \frac{\sum_i s_i}{m} \times \sum_i si + \sum_i s_i^2}{m} \times m^2 \\ &= -(\sum_i s_i)^2 + m \times \sum_i s_i^2 \end{aligned}

所以最后的答案只和后面的平方和有关。

转移还是单调队列维护下凸壳即可。

提交记录：link