給定長度為n的一段數(shù)，通過兩中操作將這段數(shù)變成排列，也就是這段數(shù)中只含有1~n，這個n可以不是原來的n

操作1 ：刪除一個數(shù)，花費(fèi)c

操作2：在任意位置加上一個任意的數(shù)，花費(fèi)d

要求花費(fèi)最小，輸出這個花費(fèi)

思路

首先我們要使得刪除和增加的操作盡可能減少, 我們要枚舉最終排列的長度, 假設(shè)為

考慮到如果有重復(fù)元素會對答案沒有貢獻(xiàn), 我們必須要刪除, 這一部分的花費(fèi)是不可避免的。假設(shè)我們?nèi)ブ夭⑴判驍?shù)組的長度為?， 并且我們叫這個數(shù)組為

接著我們可以枚舉組成最終排列長度為 1?和集合?{X} 的所有排列的花費(fèi)。其中?

于是我們會有兩種情況需要枚舉:

當(dāng)最終排列長度為 1 的時(shí)候有一種特例就是把所有元素刪除并添加一個元素 1, 此時(shí)答案為

枚舉最終排列的長度 當(dāng)最終排列長度為?p[i] = x 的時(shí)候，我們要增加 (p[i] - i) 個元素(因?yàn)槲覀兪桥藕眯虻? 使用前面有 i 個元素不用添加, 所有為 p[i] - i), 刪除 (m - i) 個元素(后面多余的元素). 即?

既要實(shí)現(xiàn)排序又要實(shí)現(xiàn)去重功能, 我們可以直接使用 set: