与题解相同,设 dpi,j 表示前 i 个数,切 j 刀,得到的最大分数
dp_{i, j} &= dp_{k, j - 1} + s_j \times \left( s_i - s_j \right) \\
&= s_i \times s_j + dp_{k, j - 1} - s_j \times s_j
\end{aligned}$$
一条斜率为 $s_i$ 的直线过点 $\left( -s_j, dp_{k, j - 1} - s_j * s_j \right)$ 的直线的截距即为 $dp_{i, j}$,维护上凸壳不行吗???为什么是下凸壳???