問題概要

$N$ 個のドアがあり、初めは全て閉じている．

Tech ちゃんは $M$ 個の魔法を使用することができる．

$i$ 番目の魔法を使用することで、 $a_{i, 1}, \ldots, a_{i, k_{i}}$ 番目の全てのドアについて開 → 閉 / 閉 → 開を行う．

各魔法の使用には金額が $c_{i}$ 円かかる．

$i$ 番目のドアが開いていたら $d_{i}$ 円もらえる場合、最終的にもらえる利益の最大を求めよ．

https://techful-programming.com/user/practice/problem/coding/10967

制約

$1 \le N \le 10$
$1 \le d_{i} \le 10^{5}$
$1 \le M \le 10^{3}$
$1 \le c_{i} \le 10^{5}$
$1 \le k_{i} \le N$
$1 \le a_{i, 1} \le \cdots \le a_{i, k_{i}} \le N$
$a_{i, j} \neq a_{i, k} \; (j \neq k)$

考えたこと

まず、魔法を 2 回唱えると元どおりになるため、同じ魔法を 2 回以上唱える必要はない．

よって、各魔法について唱える回数は 0 or 1 回であることから、ナップザック DP による解法を考える．

また、見るからに bit DP を使いそうなので、ナップザック DP と bit DP を組み合わせた DP を考える．

ナップザック DP と bit DP の解説は以下を参照．

本問題の DP の状態の持ち方、出力、初期化は次の通りになる．

状態の持ち方

$dp(i, S)$ := 最初の $i$ 個の魔法からいくつか選び、開いているドアの集合を $S$ にするための最小金額．

出力するもの

$\max_{S} { \sum_{i \in S} d_{i} - dp(N, S) }$

初期化

$dp(0, 0) = 0$
$dp(i, j) = \infty \ (i \neq 0 \wedge j \neq 0)$

#include <bits/stdc++.h>
using namespace std;

const int INF = 1 << 30;
int N, M;
int d[11], c[2000];
int mask[2000]; // i 番目の魔法による影響を受けるドアの集合
int dp[2000][2000];

int main() {
    cin >> N;
    for (int i = 0; i < N; ++i) {
        cin >> d[i];
    }
    cin >> M;
    for (int i = 0; i < M; ++i) {
        int k;
        cin >> c[i] >> k;
        for (int j = 0; j < k; ++j) {
            int a;
            cin >> a;
            mask[i] |= 1 << (a - 1);
        }
    }

    // 初期化
    for (int i = 0; i < 2000; ++i) {
        for (int j = 0; j < 2000; ++j) {
            dp[i][j] = INF;
        }
    }
    dp[0][0] = 0;

    // DP の計算
    for (int i = 0; i < M; ++i) {
        for (int S = 0; S < 1 << N; ++S) if (dp[i][S] < INF) {
            dp[i + 1][S] = min(dp[i + 1][S], dp[i][S]);
            dp[i + 1][S ^ mask[i]] = min(dp[i + 1][S ^ mask[i]], dp[i][S] + c[i]);
        }
    }

    // 出力
    int ans = 0;
    for (int S = 0; S < 1 << N; ++S) if (dp[M][S] < INF) {
        int sum = -dp[M][S];
        for (int i = 0; i < N; ++i) if (S >> i & 1) {
            sum += d[i];
        }
        ans = max(ans, sum);
    }
    cout << ans << endl;
}

類題

E - Get Everything

競プロ用

TechFUL: 春のにわとり祭り

問題概要

制約

考えたこと

状態の持ち方

出力するもの

初期化

類題