鉄則本 A23 - All Free (1Q, ★5)

dp[どこまで見たか][ビット] というタイプのビット DP。鉄則本の問題なので、コードのみ。

• 問題へのリンク

問題概要

のグリッドが与えられる。各マスは 0 または 1 である。いくつかの行を選んで、次の条件を満たすようにしたい。選ぶべき行数の最小値を求めよ (不可能な場合は -1)

【条件】
どの列についても、選んだ行のいずれかには 1 が含まれる

制約

• 
• 

コード

#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 29;

int main() {
    int N, M, a;
    cin >> N >> M;
    vector<int> A(M, 0);  // 各クーポンの情報を「ビット」で受け取る
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            cin >> a;
            if (a == 1) A[i] |= (1 << j);
        }
    }

    vector dp(1 << N, INF);
    dp[0] = 0;
    for (int i = 0; i < M; i++) {
        vector nex(1 << N, INF);
        for (int j = 0; j < (1 << N); j++) {
            nex[j] = min(nex[j], dp[j]);
            nex[j | A[i]] = min(nex[j | A[i]], dp[j] + 1);
        }
        swap(dp, nex);
    }
    cout << (dp.back() < INF ? dp.back() : -1) << endl;
}