序列分段问题

形式：一个序列分成多段，每一段按照一定方式计算权值，使总权值取最值。

基本方法：使用 $f_i$ 表示到 $i$ 的最值，根据题目加入其他维度，从 $f_{i-1}$ 或 $f_j$ 转移（$f_{i-1}\to f_i$ 即决策 $i$ 是否为断点，$f_j\to f_i$ 即决策断点为 $j$），经典形式如 $f_i=\max f_j+c(j+1,i)$。

根据两个区间之间的关系，有时需要决策本区间左端点，有时需要决策上一个区间右端点，有时二者皆可。

技巧：当每一段贡献同时与左右两端位置都有关，不妨直接在设置 $f_i$ 时令 $i$ 为区间右端点，这样枚举 $f_j$ 转移时就可以轻松计算。

  • P3628：最经典形式，设 $f_i$ 表示考虑到 $i$ 的最大权值，则 $f_i=\max_{j=1}^{i-1}f_j+a(s_i-s_j)^2+b(s_i-s_j)+c$，其中 $s$ 为 $x$ 的前缀和。
  • P3195：同样的最经典形式，状态同上，$f_i=\min_{j=1}^{i-1}f_j+(i-j-1+s_i-s_j-L)^2$，其中 $s$ 为 $C$ 的前缀和。
  • P4072：有段数限制的问题，将段数加入状态。分段后第 $i$ 段的和为 $a_i$，则题目要求最小化 $\sum a_i^2$。设 $f_{i,j}$ 为到 $i$ 已经分了 $j$ 段的最值，则 $f_{i,j}=\min_{k=1}^{i-1}f_{k,j-1}+(s_i-s_k)^2$，$s$ 为路程长度前缀和。
  • P1721：较少的数合并比较多的数合并更优，较小的数先合并比较大的数先合并更优。于是在 $h$ 排序后转为与上题类似的问题，但是 $f$ 的值要加入合并，$f_{i,j}=\max_{k=1}^{i-1}{(f_{k,j-1}+s_i-s_k)/(i-k+1)}$。
  • P4158：显然每个点都涂到一定不劣。若只有一行，也是类似的有段数限制的问题，但由于段的左端点的贡献不需要在确定右端点后产生，可以使用 $f_ {i-1}\to f_i$ 的形式转移，由于涂成的一段颜色需要相同，可以额外开一个 $0/1$ 的维度表示涂色状态（红/蓝，显然都涂色一定不劣），$f_{i,j,c_i}=\max(f_{i-1,j,c_i}+1,f_{i-1,j-1,c_i}+1,f_{i-1,j-1,\neg c_i}+1)$，$f_{i,j,\neg c_i}=\max(f_{i-1,j,\neg c_i},f_{i-1,j-1,c_i},f_{i-1,j-1,\neg c_i})$。
  • P3648：$a(b+c)+bc=c(a+b)+ab$，于是分开的顺序不影响答案。若分出的每个块块内和为 $b$，则答案为 $\sum_{i=1}^{k}b_i\sum_{j=i+1}^{k+1}b_j$。将答案对称式地乘 $2$ 并加上 $\sum b_i^2$，得到 $(\sum_{i=1}^{k+1}b_i)^2=(\sum_{i=1}^n a_i)^2$，于是答案可以转为 $\dfrac{(\sum_{i=1}^n a_i)^2-\sum_{i=1}^{k+1}b_i^2}{2}$，只需最小化 $\sum_{i=1}^{k+1}b_i^2$ 即可。于是与 P4072 相同。
  • UVA12991：区间贡献与这个区间放乒乓球还是游泳有关，将其作为 $0/1$ 加入状态。使用技巧进行转移，则 $f_{i,0}=\max_{j=1}^{i-1}f_{j,1}+g(j+1,i,P)$，$f_{i,1}=\max_{j=1}^{i-1}f_{j,0}+g(j+1,i,T)$，其中 $g(l,r,a)=(\sum_{i=l}^{\lfloor\frac{l+r}{2}\rfloor}(i-l+1)a_i)+(\sum_{i=\lfloor\frac{l+r}{2}\rfloor+1}^{r}(r-i+1)a_i)$。
  • CSP-S 2024 T3：使用技巧进行转移，则 $f_i=\max_{j=1}^{i-1}f_j+c(j,i+1)+\sum_{k=j+1}^{i-1}c(k,k+1)$。