题目

小美有一个长度为 几 的数组 Q1,Q2,..,an，他可以对数组进行如下操作:
删除第一个元素 a1，同时数组的长度减一，花费为及
·删除整个数组，花费为k*MEX(a)(其中MEX(a)表示 a 中未出现过的最小非负整数。例如0,1,2,4的MEX为3)。
小美想知道将 a 数组全部清空的最小代价是多少，请你帮帮他吧。

#include<cstdio>
#include<deque>
#include<unordered_map>
#include<algorithm>

typedef long long LL;

using namespace std;

int T, n, k, x;

unordered_map<int, int> cnt;
deque<int> nums;

LL ans = 0;

int mex(){
    for(int i=0; i<1e9; i++){
        if(cnt[i]==0) return i;
    }
    return -1;
}


// u为删除的元素个数
void dfs(int u, LL cur){
    if(cur>=ans) return;
    if(u==n+1){
        ans = cur;
        return;
    }
    dfs(n+1, cur+(LL)k*mex());
    int t = nums.front();
    nums.pop_front();
    cnt[t]--;
    dfs(u+1, cur+t);
}

int main(){
    scanf("%d", &T);
    while(T-->0){
        scanf("%d%d%d", &n, &k, &x);
        ans = 2e14;
        cnt.clear();
        nums.clear();
        for(int i=0; i<n; i++){
            int t;
            scanf("%d", &t);
            cnt[t]++;
            nums.push_back(t);
        }
        dfs(0, 0);
        printf("%lld", ans);
    }
    return 0;
}