在 CSP-S 备考的 2 - 3 个月强化训练阶段，专题突破是非常关键的一环。其中，凸包 Trick 是一个极具价值的知识点。
凸包 Trick 主要是在动态规划中利用凸包的性质来优化状态转移。凸包可以分为上凸壳和下凸壳。
先来说说凸包的概念。凸包可以简单理解为在一个平面上，给定一些点，用一条线把其中的一部分点连接起来，使得其他点都在这些线的同一侧，并且这条线的长度最短。
在动态规划中，斜率优化常常借助凸包的性质。例如，在一些问题中，我们需要维护一个单调队列来处理状态转移。对于下凸壳，其斜率是单调递增的；上凸壳则相反，斜率单调递减。
以“任务调度问题”为例来推导转移方程。假设我们有 n 个任务，每个任务有特定的执行时间和截止时间。我们的目标是在满足截止时间的前提下，使总的等待时间最短。
定义状态 dp[i] 表示完成前 i 个任务的最小等待时间。
对于第 i 个任务，我们可以考虑在前 j 个任务完成后开始执行（j < i）。那么状态转移方程可以表示为：
dp[i] = min{dp[j] + cost(j+1, i)}
其中 cost(j+1, i) 表示从第 j + 1 个任务到第 i 个任务的等待时间。
为了优化这个过程，我们可以利用凸包 Trick。通过维护一个下凸壳的单调队列，只考虑队列中的元素来进行状态转移，大大减少了计算量。
学习凸包 Trick ，首先要深入理解凸包的概念和性质，可以通过画图来直观感受。对于动态规划中的状态转移方程，要仔细分析每个状态的含义和相互关系。多做一些相关的练习题，比如经典的“加工生产调度问题”“分组背包问题”等，通过实际操作来加深对凸包 Trick 的应用能力。
总之，在 CSP-S 备考的强化训练阶段，掌握凸包 Trick 及其应用对于解决一些复杂的动态规划问题非常有帮助，希望大家能够通过精心的学习和练习，熟练运用这一技巧，提升自己的解题水平。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
