DP Part II

### 简介 这里涉及到 dp 的一些更困难的优化。 例如单调队列优化，斜率优化等。 ~~因为作者太蒟了不会四边形不等式。~~ ### 学习资料 - [我的详细讲解](https://www.luogu.com.cn/blog/205125/dong-tai-gui-hua-you-hua) - [单调队列优化dp](https://xyzl.blog.luogu.org/DQ-OP-DP) - [OI-Wiki 斜率优化](https://oi-wiki.org/dp/opt/slope/) - [【学习笔记】动态规划—斜率优化DP（超详细）](https://www.luogu.com.cn/blog/ChenXingLing/post-xue-xi-bi-ji-dong-tai-gui-hua-xie-shuai-you-hua-dp-chao-yang-x) 详细长文 - [浅谈斜率优化](https://www.luogu.com.cn/blog/ningago-lsh/xie-lv-you-hua-dp) - [斜率优化---感谢此文让我彻底弄懂斜率优化](https://blog.csdn.net/mrcrack/article/details/88252442) 入门好文 - [【一路走下去的斜率优化动态规划】](https://www.cnblogs.com/Paul-Guderian/p/7259491.html) 题目多 - [DP 优化方法大杂烩 I. ](https://www.cnblogs.com/alex-wei/p/DP_Involution.html) - [DP 优化方法大杂烩 II. ](https://www.cnblogs.com/alex-wei/p/DP_optimization_method_II.html) 总结性强 - [【学习笔记】WQS二分详解及常见理解误区解释](https://blog.csdn.net/emm_titan/article/details/124035796) ### 题单 - [DP Part I](https://www.luogu.com.cn/training/231323) - [德文的题单](https://www.luogu.com.cn/training/242460) - [斜率优化DP](https://www.luogu.com.cn/training/5352) ## 单调队列/单调栈优化 利用数据结构优化计算，在具有单调性的时候会极大加速运算，当然你至少得先会[单调队列](https://www.luogu.com.cn/training)和[单调栈](https://www.luogu.com.cn/training/238103)。 根据需要选择数据结构。 - [OI Wiki 单调队列/单调栈优化](https://oi-wiki.org/dp/opt/monotonous-queue-stack/) ### 题目 - [P1776 宝物筛选](https://www.luogu.com.cn/problem/P1776) 多重背包单调队列优化 - [P1725 琪露诺](https://www.luogu.com.cn/problem/P1725) 单调队列简单优化DP，注意到终点只要跳的到就行 - [P2627 [USACO11OPEN]Mowing the Lawn G](https://www.luogu.com.cn/problem/P2627) 注意边界 - [P3084 [USACO13OPEN]Photo G](https://www.luogu.com.cn/problem/P3084) - [P2569 [SCOI2010]股票交易](https://www.luogu.com.cn/problem/P2569) ## 斜率优化 当 $\text{DP}$ 方程为 $dp[i]=a[i]+b[j]$ 时才可用**单调队列优化**，但 $\text{DP}$ 方程为 $dp[i]=a[i] \cdot b[j]+c[i]+d[j]$ 时，由于存在 $a[i] \cdot b[j]$ 这个既有 $i$ 又有 $j$ 的项，以上方法就不适用了，这时就需要使用**斜率优化**。 - [OI Wiki 斜率优化](https://oi-wiki.org/dp/opt/slope/) ### 题目 - [P3195 [HNOI2008]玩具装箱](https://www.luogu.com.cn/problem/P3195) - [P2365 任务安排](https://www.luogu.com.cn/problem/P2365) - [P5785 [SDOI2012]任务安排](https://www.luogu.com.cn/problem/P5785) 和上一题相比可能**时光倒流**，所以上二分 - [P5017 [NOIP2018 普及组] 摆渡车](https://www.luogu.com.cn/problem/P5017) - [P4360 [CEOI2004] 锯木厂选址](https://www.luogu.com.cn/problem/P4360) - [P2120 [ZJOI2007] 仓库建设](https://www.luogu.com.cn/problem/P2120) - [P3628 [APIO2010] 特别行动队](https://www.luogu.com.cn/problem/P3628) - [CF311B Cats Transport](https://www.luogu.com.cn/problem/CF311B) ## 四边形不等式优化 （鸽） - [OI Wiki 四边形不等式优化](https://oi-wiki.org/dp/opt/quadrangle/)