状态压缩 + dp

使用状态压缩dp的情况是在数据范围不是特别大的时候，在暴力搜索不能够解决（差一点的时候，拥有dp的特征时，可以考虑）

练习题的链接https://www.luogu.com.cn/problem/P8687

#include <bits/stdc++.h>

#define ll long long

const ll N = 1e3;
ll n,m,k;
ll dp[(1 << 20) + 1];
ll v[(1 << 20) + 1];

void solve(){
    std::cin >> n >> m >> k;
    std::memset(dp,1e6,sizeof dp);
    for(ll i = 1; i <= n; i ++){
        ll h = 0;
        for(ll i = 1; i <= k; i ++){
            ll a;
            std::cin >> a;
            a -= 1;
            h |= (1 << a);
        }
        dp[h] = 1;
        v[i] = h;
    }
    for(ll i = 0; i < (1 << m); i ++){//所有可能的状态
        for(ll j = 1; j <= n; j ++){
            dp[i | v[j]] = std::min(dp[i | v[j]],dp[i] + 1);
        }
    }
    if(dp[(1 << m) - 1] >= 1e5) std::cout << -1 << "\n";
    else std::cout << dp[(1 << m) - 1] << "\n";
}

int main(){
    ll t = 1;
    while(t --)
    solve();
    return 0;
}