状压dp + 二维滚动数组

#include<bits/stdc++.h>
using namespace std;
const int N = 110, M = 1 << 20;
int f[2][M];
int a[N];
int n, m, k;
int main()
{
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= k; j ++)
        {
            int t;
            cin >> t;
            a[i] |= 1 << t - 1;
        }
    }
    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;

    for(int i = 0; i < n; i ++)
    {
        for(int j = 0; j < 1 << m; j ++)
        {
            if(f[i & 1][j] != 0x3f3f3f3f)
            {
                f[i + 1 & 1][j | a[i + 1]] = min(f[i & 1][j] + 1, f[i + 1 & 1][j | a[i + 1]]);
                f[i + 1 & 1][j] = min(f[i + 1 & 1][j], f[i & 1][j]);

            }
            f[i & 1][j] = 0x3f3f3f3f;
        }
    }

    if(f[n & 1][(1 << m) - 1] == 0x3f3f3f3f) cout << - 1 << endl;
    else cout << f[n & 1][(1 << m) - 1] << endl;
}

一维滚动

#include<bits/stdc++.h>
using namespace std;
const int N = 110, M = 1 << 20;
int f[M];
int a[N];
int n, m, k;
int main()
{
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= k; j ++)
        {
            int t;
            cin >> t;
            a[i] |= 1 << t - 1;
        }
    }
    memset(f, 0x3f, sizeof f);
    f[0] = 0;

    for(int i = 0; i < n; i ++)
    {
        for(int j = 0; j < 1 << m; j ++)
        {
            if(f[j] != 0x3f3f3f3f)
            {
                f[j | a[i + 1]] = min(f[j] + 1, f[j | a[i + 1]]);
                f[j] = min(f[j],f[j]);//可不写
            }

        }
    }

    if(f[(1 << m) - 1] == 0x3f3f3f3f) cout << - 1 << endl;
    else cout << f[(1 << m) - 1] << endl;
}