【题解】P3648 [APIO2014] 序列分割
对于这道题，我们很容易想出一个暴力 DP：
设 \(f_{i,j,k}\) 表示将区间 \([i,j]\) 切割 \(k\) 次的最大得分，\(s_i\) 表示 \(a_i\) 的前缀和。
我们可以得到一个式子：
\[f_{i,j,k} = \max_{i\leq m < j,p < k}\{f_{i,k.p} + f_{k+1,j,p} + (s_k-s_{i-1}) * (s_j-s_k)\}
\]
显然，这个式子的复杂度是 \(O(n^3k^2)\) 的，直接爆炸。
这么大的差距，我们肯定得去找个性质来优化。（明显只有找到性质才能逼近正解）
我们考虑区间 \(A,B,C\) 的合并，我们记 \(a,b,c\) 分别为三个区间的区间和。
- \(AB~|~C \to (a+b) \times c + a \times b = ab + ac + bc\)
- \(A~|~BC \to a\times (b+c) + b \times c = ab + ac + bc\)
所以说，从上面的式子来看，我们其实并不需要关心将块分开的顺序，只需要关心从哪些位置分开。
因此，我们便可以将状态简化为：设 \(f_{i,j}\) 表示将前 \(i\) 个数切割 \(j\) 次的最大收益，并可以得到式子如下：
\[f_{i,j} = \max_{k < i}\{f_{k,j-1} + s_k \times (s_i-s_k)\}
\]
我们可以发现，这个式子满足 \(y = kx +b\) 的性质，可以进行斜率优化。
写成斜率优化的式子：
\[f_{k,j-1} - s_k^2= -s_k\times s_i + f_{i,j}
\]
因为是求 \(b\) 的最大值，所以维护上凸包。
最后输出方案只需要每次将决策点记下即可。