CF833B The Bakery
令 \(f_{i,k}\) 表示前 \(i\) 个数字分成 \(k\) 段的最大总价值，显然有暴力转移 \(f_{i,k}=f_{j,k-1}+kind(j+1,i)\)，其中 \(kind(x,y)\) 表示 \([x,y]\) 中不同数字的种数。
但暴力转移是 \(O(n^2k)\) 的，考虑把 \(kind\) 函数拆开优化，把每种数字的贡献对应到区间中该种数字第一次出现的位置。对于数字 \(a_i\)，其对 DP 数组产生贡献的范围是 \([pre_i,i)\)，这部分转移过来能得到没出现过的数字 \(a_i\)。
先枚举 \(k\)，再枚举 \(n\)，用线段树维护上一轮的 DP 数组加上转移的贡献，前缀 \(\max\) 即为当前 DP 值。
标签：kind,数字,贡献,枚举,动态,规划,转移,DP From： https://www.cnblogs.com/landsol/p/17911387.html