CWOI 杂题选做(23May,23Jun)
CF833B The Bakeryψ(｀∇´)ψ
将一个长度为 \(n\) 的序列分为 \(k\) 段，使得总价值最大。
一段区间的价值表示为区间内不同数字的个数。
\(n\leq 35000,k\leq 50\)
Translated by @ysner @yybyyb
考虑一个比较简单的暴力 dp：设 \(dp(i, j)\) 表示，考虑前 \(i\) 个位置，分成 \(j\) 段的最大价值。
枚举上一个端点即可转移：\(dp(i, j) = \max\limits_{k = j - 1}^{i - 1}\{dp(k, j - 1) + F(k + 1, i)\}\)。
先不管里面怎么弄，先把外面决策集合优化一下，注意到如果固定 \(i\)，那么当 \(j + 1\) 的时候，决策集合会少 \(O(k)\) 数量级的状态，这是不好做的。
那么固定 \(j\)，观察当 \(i + 1\) 时的决策集合变化：只是多了一个 \(dp(i, j - 1)\)，\(O(1)\) 变化，于是我们选择固定 \(j\)，以 \(j\) 作为阶段。
之后考虑怎么优化 \(F\) 的计算，这个东西单独计算是方便的，但是我们现在将其加到了方程中，它也没法以多项式的形式展开进行优化。
所以我们不妨换个思路，既然正着算 \(F\) 算不了，我们为什么不考虑反着算 \(F\) 的贡献，即，考虑每一个位置 \(i\) 能对哪些状态造成贡献，我们直接把这个贡献加到对应的 dp 数组里面。
可以注意到，一个 \(a_i\) 的贡献应当是对 \(dp(pre(a_i) + 1 \sim i, j - 1)\) 造成的，其中 \(pre\) 是上一个 \(a_i\) 的位置。
因为我们当前只枚举到 \(i\)，所以这个影响是有上界的，依次加入可以证明这样做的正确性。
于是我们枚举 \(j\)，枚举 \(i\)，对每个 \(i\) 在线段树上修改贡献，然后转移直接询问 \(\max\) 即可。