状压dp

灵感由ac狗激发

#include<bits/stdc++.h>
using namespace std;
const int N=1<<20;
int dp[N];
vector<int>a;
int main(){
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=0;i<n;i++){
        int mk=0;
        for(int j=0;j<k;j++){
            int x;cin>>x;
            mk|=(1<<--x);
        }
        a.push_back(mk);
    }
    fill(dp,dp+N,10000);
    dp[0]=0;
    for(int i=0;i<n;i++){
        int p=a[i];
        for(int mk=(1<<m)-1;mk>=0;mk--){
            if(dp[mk]<10000){
                dp[mk|p]=min(dp[mk|p],dp[mk]+1);
            }
        }
    }
    if(dp[(1<<m)-1]==10000)cout<<-1;
    else cout<<dp[(1<<m)-1];
    return 0;
}