受限于在线编辑器的性能瓶颈（省流：写太多了会很卡），在此决定把另外的（不在算法提高课中）DP斜率优化题目单独拎出来写一篇做题笔记。旨在记录算式消元换元的原则与技巧、凸包维护的方法。题目大致由易到难。
洛谷 P3195 [HNOI2008] 玩具装箱
题目地址：P3195
题目难度：省选/NOI-
P 教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。
P 教授有编号为
的 件玩具，第 件玩具经过压缩后的一维长度为 。 为了方便整理，P教授要求：
- 在一个一维容器中的玩具编号是连续的。
- 同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物。形式地说，如果将第
件玩具到第 个玩具放到一个容器中，那么容器的长度将为 。 制作容器的费用与容器的长度有关，根据教授研究，如果容器长度为
，其制作费用为 。其中 是一个常量。P 教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过 。但他希望所有容器的总费用最小。 输入格式：
第一行有两个整数，用一个空格隔开，分别代表
和 。 第
到 第 行，每行一个整数，第 行的整数代表第 件玩具的长度 。 输出格式：
输出一行一个整数，代表所有容器的总费用最小是多少。
数据结构：
对于全部的测试点，
， ， 。
这道题就和《任务安排》一个模子了。设计状态为选前 dp[i] = min(dp[i], dp[j] + (i - j - 1 + sumC[i] - sumC[j] - L) * (i - j - 1 + sumC[i] - sumC[j] - L))。
对等式进行化简：
考虑到
发现一组同构，令
然后拆括号：
我们的斜率需要一个只和循环变量
此时直线方程的每个要素都很明了了。因为
- 创建一个双端队列来存放凸包上的点的下标
- 如果队头元素满足
，则弹出队头。因为队头所维护的点的斜率已经失去最优性，在单调递增的斜率意义下不会再被用到。 - 如果队尾元素满足
，则弹出队尾。因为引入的新点 使得原先维护的最值点不再最值，类比单调队列中不符合单调性时的弹出操作。
为了避免如上除法操作带来精度影响，故采用交叉相乘法。此时就需要注意相乘结果是否会爆类型。
推式子时居然把斜率弄成了
洛谷 P3628 [APIO2010] 特别行动队
题目地址：P3628
题目难度：省选/NOI-
题目来源：APIO 2010
你有一支由
名预备役士兵组成的部队，士兵从 到 编号，你要将他们拆分成若干特别行动队调入战场。出于默契的考虑，同一支特别行动队中队员的编号应该连续，即为形如 的序列。所有的队员都应该属于且仅属于一支特别行动队。 编号为
的士兵的初始战斗力为 ，一支特别行动队的初始战斗力 为队内士兵初始战斗力之和，即 。 通过长期的观察，你总结出对于一支初始战斗力为
的特别行动队，其修正战斗力 ，其中 是已知的系数（ ）。 作为部队统帅，现在你要为这支部队进行编队，使得所有特别行动队的修正战斗力之和最大。试求出这个最大和。 输入格式：
输入的第一行是一个整数
，代表士兵的人数。 输入的第二行有三个用空格隔开的整数，依次代表
，即修正战斗力的系数。 输入的第三行有
个用空格隔开的整数，第 个整数代表编号为 的士兵的初始战斗力 。 输出格式：
输出一行一个整数，代表最大的所有特别行动队战斗力之和。
数据范围：
对于
的数据， 。 对于
的数据， 对于
的数据， ， ， ， ， 。
写出暴力状态转移方程：dp[i] = max(dp[i], dp[j] + a * X * X + b * X + c)，其中
那么斜率就是
类比先前推导过的最小化截距的方法，我们可以轻松得出一个结论——截距最大化，维护上凸壳！自己画个图可以知道，我们需要找的最值点就是第一个斜率小于当前直线斜率的点。观察到
