2021.11.13/dfs/糖果
https://www.acwing.com/problem/content/description/1245/
真无语啊，明明dp更加简单，我却被dfs + ida*折磨

#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
int a[120], n, m, k, ans = 30, ed, x, ida[1048576], counts;
int low(int x){//返回x的二进制中 1 的个数
    int ret = 0;
    for(; x; x ^= (x & -x)) ret++; 
    return ret;
}
void dfs(int cus, int kinds, int idx){//cus：当前包数，kinds：当前组合，idx当前数组下标初始值
    if(cus >= ans || ida[kinds] <= cus) return;//如果大于答案 或者 糖果组合有过更优解
    if(kinds == ed) {ans = cus;return;} 
    ida[kinds] = cus;//更新糖果组合的最小值
    for(int i = idx; i < n; i++)
        if((kinds | a[i]) != kinds) dfs(cus + 1, (kinds | a[i]), i + 1);
}
int main(){
    cin >> n >> m >> k;
    ed = (1 << m) - 1;//所有糖果都有的最终状态
    for(int i = 0; i < n; i++)
        for(int j = 0; j < k; j++)
            cin >> x, a[i] |= (1 << (x - 1));
    sort(a, a + n, [](const int& p, const int& q){return low(p) > low(q);});//对每包糖果的种类数进行排序
    memset(ida, 0x3f, sizeof ida);//初始化ida数组，就是糖果组合的选择数
    dfs(0, 0, 0);
    cout << (ans == 30 ? -1 : ans);
    return 0;
}

// 亏我tm写这么多估计函数 TLE，其实不需要
// vector[HTML_REMOVED] pq;
// for(int i = idx; i < n; i++){
// int tmp = (kinds | a[i]);
// if(tmp != kinds) pq.push_back({1e9 - low(tmp - (tmp & kinds)) * 200 + i, i});
// }
// sort(pq.begin(), pq.end());
// for(auto [_,i] : pq)
// dfs(cus + 1, kinds | a[i], i + 1);
//2097152 1 << 21
//1048576 1 << 20