题目描述
一道不限段数的分段问题，要求给出 \(n\) 个元素，求出分任意组所产生的最小代价。
思路
我们可以分为两步来求解这个问题，暴力转移与优化。
The First Step 暴力转移
考虑暴力DP，根据题目描述，每个容器之中玩具的编号都是连续的，并且不限容器数量，状态就很好定义了，我们令 \(dp_i\) 表示前 \(i\) 个玩具全部放入容器的最小花费，每次转移时枚举上一个容器中最后一个玩具的位置，再加上当前容器的花费即可，我们就可以列出形如 \(dp_i=\max_{0 \le j \le i-1} {dp_j+val_{i,j}}\) 的状态转移方程，那么现在的问题就在于如何求花费。
观察题目给出的式子我们发现，容器长度 \(x\) 含有第 \(i\) 到 \(j\) 个元素的求和，快速求解区间和的问题我们需要使用前缀和来维护上式，注意因为还有 \(j-i\) 的存在，我们可以将每个元素加一再求前缀和，这样一来后续的拆式子优化会更加简便。
最后，我们再将求得的 \(x\) 根据题目要求减 \(L\) 再平方即可，令 \(f_i\) 表示前 \(i\) 个数分别加一的前缀和，最终可以列出状态转移方程为 $$dp_i=\max_{0 \le j \le i-1} {dp_j+(f_i-f_j-l)^2}$$ 实现非常简单，时间复杂度 \(O(n^2)\) 无法接受，考虑优化。
The Second Step 优化
对于诸如此类含有平方项和交叉项的状态转移方程，我们很难直接使用单调队列等一些数据结构直接进行优化，那么这里就要给出一种新的优化方式斜率优化，顾名思义，我们将状态转移方程看作一个 \(y=kx+b\) 的一次函数形式，其中 \(y\) 与 \(x\) 是未知位置的项，\(k\) 与 \(b\) 是已知位置的项，对应到转移方程里也就是 \(y\) 和 \(x\) 对应与 \(j\) 有关的式子， \(k\) 和 \(b\) 对应与 \(i\) 有关的式子，交叉项构成 \(kx\)，平方项与DP值（非交叉项）构成 \(y\) 和 \(b\)。
不难得出，我们想要让 \(dp_i\) 最小，就是让 \(b\) 最小，也就是令一次函数的截距最小，我们将每个状态 \(i\) 看作一个横坐标为 \(x_i\)，纵坐标为 \(y_i\) 的点，该问题就可以转换为，对于一条已知斜率为 \(k\) 的直线，匹配到一个点 \((x,y)\)，使得截距 \(b\) 最小。
以该题为例，将状态转移方程展开，令 \(j\) 为最优决策点，可以得到 \(dp_i=dp_j+(f_i-L)^2-2 \cdot (f_i-L) \cdot f_j+f_j^2\)，移项得 \(dp_j+f_j^2=2 \cdot (f_i-L) \cdot f_j+dp_i-(f_i-L)^2\)，那么根据前面的分析，\(dp_i-(f_i-L)^2\) 就可以表示为 \(b\)，\(2 \cdot (f_i-L)\) 就可以表示为 \(k\)，\(f_j\) 就可以表示为 \(x\)，\(dp_j+f_j^2\) 就可以表示为 \(y\)。对于每个决策 \(i\) 我们就可以表示为一个 \((f_i,dp_i+f_i^2)\) 的点。
想象一下，对于许多排布在平面直角坐标系上的点，一条斜率为 \(k\) 的直线从纵坐标为负无穷的位置自下向上移动，这过程中截距 \(b\) 在不断增大，那么直线遇到的第一个点就是要找的目标点，观察对于斜率不同的直线所找到的全部目标点，不难发现，将最外层的各点围成一个包含所有点的凸多边形，匹配到的目标点一定在这个凸多边形的下半部分上，即一个由最外层点组成的下凸包，那么内部的点便都没有用处了，我们可以通过一些数据结构来维护这个下凸包即可。
以上分析的是求最小值的题目，若是求最大值反过来采用上凸包即可。