P8687 [蓝桥杯 2019 省 A] 糖果

题意：n个零食，每个零食有k种配料，一共有m种配料。问最少吃几包零食，可以吃到所有配料。
n <= 100, m <= 20, k <= m。

思路：最优化问题，如果n <= 20可以直接bf，这里m <= 20，对m进行状态压缩，正确的解法应该是线性dp + 状态压缩。

总结：很容易陷入一个哈密顿路径思路的误区中，在哈密顿路径中，一个bit可以代表一个站点。状态的转移比较容易理解。在这个里面，bit位跟零食id没有联系，所以不能这么考虑。

https://www.luogu.com.cn/problem/P8687

void solve(){
    int n, m, k;
    cin >> n >> m >> k;

    vector<int> a(n, 0);
    for (int j = 0; j < n; ++j) for (int i = 0; i < k; ++i){
        int t;
        cin >> t;
        t --;
        a[j] |= (1 << t);
    }

    vector<int> ans(1 << m, 0x3f3f3f3f);
    ans[0] = 0;
    int s = (1 << m) - 1;
    set<int> sett;
    sett.insert(0);
    for (int i = 0; i < n; ++i){
        for (int j = 0; j < s; ++j){
            ans[j | a[i]] = min(ans[j | a[i]], ans[j] + 1);
        }
    }
    cout << (ans[s] != 0x3f3f3f3f ? ans[s] : -1) << endl;
}