Jellyfish and Mex (Codeforces 1875D)
Tags: DP, dp

You are given an array of $$$n$$$ nonnegative integers $$$a_1, a_2, \dots, a_n$$$. Let $$$m$$$ be a variable that is initialized to $$$0$$$, Jellyfish will perform the following operation $$$n$$$ times:  select an index $$$i$$$ ($$$1 \leq i \leq |a|$$$) and delete $$$a_i$$$ from $$$a$$$.  add $$$\operatorname{MEX}(a)^{\dagger}$$$ to $$$m$$$. Now Jellyfish wants to know the minimum possible final value of $$$m$$$ if he performs all the operations optimally.$$$^{\dagger}$$$ The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:  The MEX of $$$[2,2,1]$$$ is $$$0$$$, because $$$0$$$ does not belong to the array.  The MEX of $$$[3,1,0,1]$$$ is $$$2$$$, because $$$0$$$ and $$$1$$$ belong to the array, but $$$2$$$ does not.  The MEX of $$$[0,3,1,2]$$$ is $$$4$$$ because $$$0$$$, $$$1$$$, $$$2$$$, and $$$3$$$ belong to the array, but $$$4$$$ does not. 

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 5000$$$). The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 5000$$$) — the size of the array.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) — the integers in the array.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.

Output: For each test case, output a single integer — the minimum value of $$$m$$$ if the operations are performed optimally.

Note: In the first test case, we delete elements from $$$a$$$ in the following order: $$$[5,2,\color{red}{1},0,3,0,4,0] \to [5,2,0,3,\color{red}{0},4,0] \to [5,2,\color{red}{0},3,4,0] \to [5,2,3,4,\color{red}{0}] \to [5,2,\color{red}{3},4] \to [\color{red}{5},2,4] \to [\color{red}{2},4] \to [\color{red}{4}] \to [~]$$$. The value of $$$m$$$ will be $$$1+1+1+0+0+0+0+0=3$$$.

Sample Inputs:
4
8
5 2 1 0 3 0 4 0
2
1 2
5
1 0 2 114514 0
8
0 1 2 0 1 2 0 3

Sample Outputs:
3
0
2
7

Solution (Python):
""""""
from sys import stdin, stdout
for _ in range(int(input())):
    n = int(input())
    c = [0] * (n + 1)
    move = [True] * (n + 1)
    for x in map(int, stdin.readline().split()):
        if x <= n:
            c[x] += 1
    if c[0] <= 1:
        stdout.write('0\n')
        continue
    min_before = float('inf')
    for i in range(n + 1):
        if c[i] >= min_before:
            move[i] = False
        elif c[i] == 0:
            break
        else:
            min_before = c[i]
    dp = [float('inf')] * i + [0]
    for j in range(i, -1, -1):
        if move[j]:
            for k in range(j, i + 1):
                if move[k]:
                    dp[j] = min(dp[j], dp[k] + k * (c[j] - 1) + j)
    stdout.write(str(dp[0]) + '\n')

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    dic = {}
    for i in map(int, input().split()):
        if i in dic:
            dic[i] += 1
        else:
            dic[i] = 0
    if 0 not in dic:
        print(0)
        continue
    dp = [0, dic[0]]
    is_min = [(dic[0], 0)]
    min_num = dic[0]
    i = 1
    while i in dic:
        if dic[i] < min_num:
            is_min.append((dic[i], i))
            min_num = dic[i]
        i += 1
    i = 1
    while i in dic:
        ls = []
        for (a, b) in is_min:
            if b > i:
                break
            ls.append(a * (i + 1) + b + dp[b])
        dp.append(min(ls))
        i += 1
    print(dp[-1])

Solution (Python):
""""""
for _ in range(int(input())):
    n = int(input())
    l = list(map(int, input().split()))
    (check, flag) = ([0] * (n + 1), [True] * (n + 1))
    for i in l:
        if i <= n:
            check[i] += 1
    if not check[0]:
        print(0)
        continue
    minn = float('inf')
    for i in range(n + 1):
        if not check[i]:
            break
        elif check[i] < minn:
            minn = check[i]
        else:
            flag[i] = False
    dp = [float('inf')] * i + [0]
    for j in range(i, -1, -1):
        if not flag[j]:
            continue
        for k in range(j, i + 1):
            if not flag[k]:
                continue
            dp[j] = min(dp[j], dp[k] + k * (check[j] - 1) + j)
    print(dp[0])