The Bakery 题解

思路

设 $dp_g(i)$ 表示把前 $i$ 个蛋糕划分成 $g$ 个非空盒子的最大价值。转移为

$$dp_g(i)=\max_{g-1\le j<i}\{dp_{g-1}(j)+distinct(j+1,i)\}.$$

固定层数 $g$，从左到右加入位置 $i$。设 $p$ 是 $a_i$ 上一次出现的位置。对切分点 $j\in[p,i-1]$，新区间 $(j,i]$ 之前不含 $a_i$，加入它后不同值数增加一；对 $j<p$ 则不变。因此，只需对候选切分点区间 $[p,i-1]$ 整体加一，再查询 $[g-1,i-1]$ 的最大值。

用支持区间加和区间最大值的懒标记线段树维护所有候选切分点，即可完成一层 DP。

做法

1. 初始化上一层 $dp_0(0)=0$，其余状态不可达。
2. 对每个盒子数 $g=1,2,\ldots,k$，用上一层 DP 值建立线段树，并清空每个种类的上次出现位置。
3. 依次扫描 $i=1,2,\ldots,n$，将区间 $[last_{a_i},i-1]$ 加一，再查询合法切分点区间的最大值作为 $dp_g(i)$。
4. 最终输出 $dp_k(n)$。

正确性证明

加入右端点 $i$ 时，对于切分点 $j$，新区间为 $(j,i]$。当且仅当 $j$ 不小于 $a_i$ 的上次出现位置时，$(j,i-1]$ 中没有 $a_i$，所以加入 $a_i$ 会使不同种类数增加一。线段树的区间加恰好对全部且仅这些候选转移增加一。

线段树叶子 $j$ 在扫描到 $i$ 后因此等于 $dp_{g-1}(j)+distinct(j+1,i)$。查询所有合法 $j\in[g-1,i-1]$ 的最大值，正是 DP 转移式。逐层归纳可知所有状态正确，故 $dp_k(n)$ 是恰好划分成 $k$ 段的最大价值和。

复杂度

每层执行 $n$ 次区间加和最大值查询，时间复杂度为 $O(kn\log n)$，空间复杂度为 $O(n)$。