摘要
DP 优化的核心思想:在状态转移时及时排除不可能最优的决策,保持候选集合的有效性和秩序性。
倍增优化
有点复杂,先跳过:【紫色】P1081 [NOIP 2012 提高组] 开车旅行 - 洛谷。
单调队列优化
OI 是一个单调队列,如果有人比你年龄小,还比你强,那么你应该出列了。
单调队列维护可行决策集合基于这一思想:如果:
比 总是更容易符合转移条件; 比 的收益总是更不差 那么
总是一个比 更好的选择,此时 应该出列。
对于状态转移方程模型:
且
【蓝色】P10978 Fence - 洛谷 状态转移方程如下:
【紫色】P10977 Cut the Sequence - 洛谷 状态转移方程如下:
单调栈的使用与单调队列基本类似:
单调栈 | 单调队列 | |
---|---|---|
方程性质 | 导函数递增、求最大值(P5504 [JSOI2011] 柠檬 - 洛谷),或者导函数递减、求最小值 | 函数递增、求最小值(P10977 Cut the Sequence - 洛谷),或者导函数递减、求最大值(P10978 Fence - 洛谷) |
决策性质 | 决策 |
决策 |
斜率优化
对于状态转移方程模型:
且
【紫色】P3195 [HNOI2008] 玩具装箱 - 洛谷 状态转移方程如下:
【紫色】P5785 [SDOI2012] 任务安排 - 洛谷 状态转移方程如下:
【黑色】P3571 [POI 2014] SUP-Supercomputer - 洛谷 计算公式如下:
四边形不等式优化
对于状态转移方程模型:
若
则
虚假的单调性:证明其满足四边形不等式然后推导单调;
真正的单调性:暴力打印
然后找规律发现单调性。
其中
满足四边形不等式。
【紫色】P4767 [IOI 2000] 邮局 加强版 - 洛谷
其中,
满足四边形不等式。
DP 杂题选讲
【黑色】P10197 [USACO24FEB] Minimum Sum of Maximums P - 洛谷
备用题单
TODO:【黑色】P8864 「KDOI-03」序列变换 - 洛谷
TODO:【紫色】P1357 花园 - 洛谷
TODO:【黑色】P1721 [NOI2016] 国王饮水记 - 洛谷
目前暂无正解:【黑色】P2145 [JSOI2007] 祖玛 - 洛谷
TODO:【黑色】P8275 [USACO22OPEN] 262144 Revisited P - 洛谷
TODO:【黑色】P8194 [USACO22FEB] Phone Numbers P - 洛谷