Content：dp优化
Date：2025.7.26
例题
洛谷-P1886 滑动窗口
思路
直接单调队列维护即可，具体操作如下：
- 每次查看队尾的元素，维护单调性。
- 对于队头不在当前滑动窗口的元素，弹出。
提交记录：link
洛谷-P2365 任务安排
思路
定义 \(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
洛谷-P10979 任务安排 2
思路
\(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
洛谷-P5785 [SDOI2012] 任务安排
思路
注意数据范围，\(\lvert T_i \rvert \le 2^8\)，所以 \(T_{i}+s\) 不具有单调性，所以上面面直接维护的方法不可做。于是我们考虑直接维护整个下凸壳，对于转移时，二分查找就可以了。
提交记录：link
洛谷-P4072 [SDOI2016] 征途
思路
我们定义 \(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