题解：AT_arc130_e [ARC130E] Increasing Minimum

thousands_of_years · 2026-04-21 17:18:06 · 题解

solution

对 DaiRuiChen007 题解更加详细的解释与补充。

首先答案形式明确了。我们要把序列划分为若干个集合 S_1, S_2, \dots, S_k 使得对于 i < k - 1 均有 S_i \subseteq S_{i+1} 且每个集合都没有重复元素。注意 i = k - 1 时则不必满足。

我们设的 f_i 并不是表示 b[1,i] 的最小划分轮数，而是划分轮数，意思是当一段区间是能够完全划分（就是最后一段划分仍然要满足条件），只存在一种划分方案。

证明：我们从每个元素进行考虑，那么元素出现个数的最大值就是这个划分轮数，每种的元素出现位置归属集合，按照 S_{k-cnt_i+1}, S_{k-cnt_i+1}, \dots, S_k 的方式给对应集合。

注意到答案 i = k - 1 时则不必满足。那么我们直接枚举倒数第二轮的最靠右的满足条件的划分界限。

证明：仍然从上方的证明出发，发现答案 i = k - 1 时则不必满足时，除了最大出现次数元素不能够改变集合（主要是都占满了还咋变），否则就是选择是否留一个给最后那个集合，显然肯定是不留是最优的，这样能使得 A_i 减少 1，所以说那个字典序就是个诈骗，不留对应的就是倒数第二轮包含的尽可能多，划分界限最靠右。

枚举倒数第二段的划分界限，DaiRuiChen007 的判断方法是 dp[i]<dp[o]，这里的意思不是倒数第二轮的划分轮次有差异，倒数第二轮的划分轮次是固定的，比最大出现次数小 1。