Problem - D - Codeforces 题目大意:有一个n个数的数组a,数m初始为0,每次操作可以删除任意一个数,然后m加上那个数,求n次操作和m的最小值 1<=n<=5000;0<=a[i]<=1e9 思路:可以发现,如果我们要删除某个数,那么一定要把所有和这个数相等的数全部删去,这样才能使MEX变小,同时,所有大于MEX的数删去的花费都是0,所以我们每次操作的数的大小都是递减的
题面 分析: 题目最终需要达到MEX位0,也就是从最开始的MEX变成0后m的最小值,可以设 d p i dp_i dpi表示当前MEX为 i i i时,m的最小值,那么就可以根据前一个状态推出后一个状态,也就是假如当前MEX是 i i i,那么对于1~ i i i之间的 j j j的所有每一种可能的MEX,都会有一个权值对应得到 d p j dp_j dpj取最小值得到最小的m值,状态转移