特别行动队

考点：斜率优化

题意：有个正整数，请分成若干段，每段的总和为，价值为，求最大总价值。。

考虑动态规划，表示前个队员产生的最大价值，则显然

最终答案为，利用前缀和可以实现求，时间复杂度。

考虑到瓶颈主要在于状态转移时，最佳状态无法快速找到，所以尝试斜率优化。

观察转移方程：

经过展开、移项可以化为：

然后一眼就可以看出来，这个式子有点类似直线的表达式：

当我们选定时，显然确定了，并且越小，越小。那么把这个问题放在平面上，就是确定了直线的斜率，且直线必须经过某个定点，最小化它的斜率。

注意到是负数，也就是单调递减且始终为负，而且，那么这是斜率优化的经典模型，时间复杂度优化到。

总结斜率优化的技巧如下：

将原方程式展开移项，保证右边只和被转移的状态有关，左边状态只能加减常数。其次要使斜率单调，才能快速维护。最后注意细节，刚开始应当往队列里插入一个，并且注意X和Y的值也应当为0。