CF Round 4 (Div. 1 + Div. 2) C. Make It Permutation (思维+排序+枚举)

给定长度为n的一段数，通过两中操作将这段数变成排列，也就是这段数中只含有1~n，这个n可以不是原来的n

操作1 ：删除一个数，花费c

操作2：在任意位置加上一个任意的数，花费d

要求花费最小，输出这个花费

思路

首先我们要使得删除和增加的操作尽可能减少, 我们要枚举最终排列的长度, 假设为

考虑到如果有重复元素会对答案没有贡献, 我们必须要删除, 这一部分的花费是不可避免的。假设我们去重并排序数组的长度为 ， 并且我们叫这个数组为

接着我们可以枚举组成最终排列长度为 1 和集合 {X} 的所有排列的花费。其中 

于是我们会有两种情况需要枚举:

当最终排列长度为 1 的时候有一种特例就是把所有元素删除并添加一个元素 1, 此时答案为

枚举最终排列的长度 当最终排列长度为 p[i] = x 的时候，我们要增加 (p[i] - i) 个元素(因为我们是排好序的, 使用前面有 i 个元素不用添加, 所有为 p[i] - i), 删除 (m - i) 个元素(后面多余的元素). 即 

既要实现排序又要实现去重功能, 我们可以直接使用 set: